Essa é uma “regra” apropriada para identificar a notação “grande O” de um algoritmo?

Aprendi mais sobre o Big O Notation e como calculá-lo com base em como um algoritmo é escrito. Me deparei com um conjunto interessante de "regras" para o cálculo de uma notação Big O de algoritmos e queria ver se estou no caminho certo ou a caminho.

Notação grande O: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Notação grande O: N ²

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Notação grande O: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Notação grande O: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

Meus exemplos e a notação subseqüente estão corretos? Existem anotações adicionais das quais devo estar ciente?

Formalmente, a notação big-O descreve o grau de complexidade.

Para calcular a notação big-O:

1. identificar fórmula para a complexidade do algoritmo. Digamos, por exemplo, dois loops com outro aninhado dentro, depois outros três loops não aninhados:2N² + 3N
2. remova tudo, exceto o termo mais alto: 2N²
3. remova todas as constantes: N²

Em outras palavras, dois loops com outro aninhado por dentro, e outros três loops não aninhados é O (N²)

Obviamente, isso pressupõe que o que você tem em seus loops são instruções simples. Se você tem, por exemplo, sort()dentro do loop, terá que multiplicar a complexidade do loop pela complexidade da sort()implementação usada pela linguagem / biblioteca subjacente.

Se você deseja analisar esses algoritmos, precisa definir // dostuff, pois isso pode realmente mudar o resultado. Suponhamos que o dostuff exija um número O (1) constante de operações.

Aqui estão alguns exemplos com esta nova notação:

Para o seu primeiro exemplo, a travessia linear: isso está correto!

EM):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Por que é linear (O (n))? À medida que adicionamos elementos adicionais à entrada (matriz), a quantidade de operações acontecendo aumenta proporcional ao número de elementos que adicionamos.

Portanto, se for necessária uma operação para incrementar um número inteiro em algum lugar da memória, podemos modelar o trabalho que o loop realiza com f (x) = 5x = 5 operações adicionais. Para 20 elementos adicionais, fazemos 20 operações adicionais. Uma única passagem de uma matriz tende a ser linear. O mesmo ocorre com algoritmos como a classificação de bucket, que são capazes de explorar a estrutura dos dados para fazer uma classificação em uma única passagem de uma matriz.

Seu segundo exemplo também estaria correto e terá a seguinte aparência:

O (N ^ 2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

Nesse caso, para cada elemento adicional na primeira matriz, temos que processar TODOS os j. A adição de 1 a i adiciona (comprimento de j) a j. Assim, você está correto! Esse padrão é O (n ^ 2), ou, no nosso exemplo, é realmente O (i * j) (ou n ^ 2 se i == j, o que geralmente acontece com operações de matriz ou uma estrutura de dados quadrada.

Seu terceiro exemplo é onde as coisas mudam, dependendo do material; Se o código é como está escrito e o material é uma constante, na verdade é apenas O (n) porque temos 2 passagens de uma matriz de tamanho n, e 2n reduz-se a n. Os loops que estão fora um do outro não é o fator chave que pode produzir código 2 ^ n; Aqui está um exemplo de uma função que é 2 ^ n:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

Esta função é 2 ^ n, porque cada chamada para a função produz DUAS chamadas adicionais para a função (Fibonacci). Toda vez que chamamos a função, a quantidade de trabalho que temos que fazer dobra! Isso cresce super rápido, como cortar a cabeça de uma hidra e ter duas novas brotando a cada vez!

Para o seu exemplo final, se você estiver usando uma classificação nlgn como merge-sort, está certo de que esse código será O (nlgn). No entanto, você pode explorar a estrutura dos dados para desenvolver classificações mais rápidas em situações específicas (como em um intervalo conhecido e limitado de valores, como de 1 a 100). Você está certo ao pensar, no entanto, que o código de ordem mais alta domina; portanto, se uma classificação O (nlgn) estiver próxima a qualquer operação que leve menos que O (nlgn), a complexidade total do tempo será O (nlgn).

Em JavaScript (pelo menos no Firefox), a classificação padrão em Array.prototype.sort () é de fato MergeSort, portanto, você está olhando O (nlgn) para o seu cenário final.

Seu segundo exemplo (loop externo de 0 a n , loop interno de 0 a b ) seria O ( nb ), não O ( n ² ). A regra é que você está computando algo n vezes, e para cada um deles você está computando algo mais b vezes, portanto, o crescimento dessa função depende apenas do crescimento de n * b .

Seu terceiro exemplo é apenas O ( n ) - você pode remover todas as constantes, pois elas não crescem com ne o crescimento é o objetivo da notação Big-O.

Quanto ao seu último exemplo, sim, sua notação Big-O certamente virá do método de classificação que será, se for baseado em comparação (como geralmente é o caso), em sua forma mais eficiente, O ( n * logn ) .

Lembre-se de que esta é uma representação aproximada do tempo de execução. A "regra geral" é aproximada porque é imprecisa, mas fornece uma boa aproximação de primeira ordem para fins de avaliação.

O tempo de execução real dependerá de quanto espaço de pilha, qual a velocidade do processador, conjunto de instruções, uso de operadores de prefixo ou incremento pós-correção, etc., yadda. A análise adequada do tempo de execução permitirá a determinação da aceitação, mas o conhecimento do básico permite que você programe desde o início.

Concordo que você está no caminho certo para entender como o Big-O é racionalizado de um livro para uma aplicação prática. Esse pode ser o obstáculo difícil de superar.

A taxa de crescimento assintótica se torna importante em grandes conjuntos de dados e programas grandes; portanto, para exemplos típicos, você demonstra que não é tão importante para a sintaxe e a lógica adequadas.

Grande oh, por definição, significa: para uma função f (t) existe uma função c * g (t) onde c é uma constante arbitrária tal que f (t) <= c * g (t) para t> n onde n é uma constante arbitrária, então f (t) existe em O (g (t)) .Esta é uma notação matemática usada na ciência da computação para analisar algoritmos. Se você está confuso, eu recomendaria olhar para os relacionamentos de fechamento, dessa forma, você pode ver em uma visão mais detalhada como esses algoritmos obtêm esses valores altos.

Algumas conseqüências dessa definição: O (n) é realmente congruente com O (2n).

Também existem muitos tipos diferentes de algoritmos de classificação. O valor mínimo de Big-Oh para uma classificação de comparação é O (nlogn), no entanto, existem muitos tipos com pior big-oh. Por exemplo, a classificação da seleção tem O (n ^ 2). Algum tipo de comparação não pode ter melhores valores de oh grande. Uma classificação de bucket, por exemplo, tem O (n).