Big O, como você o calcula / aproxima?

A maioria das pessoas com um diploma em CS certamente saberá o que Big O significa . Isso nos ajuda a medir a escala de um algoritmo.

Mas estou curioso, como você calcula ou aproxima a complexidade de seus algoritmos?

Eu farei o meu melhor para explicá-lo aqui em termos simples, mas esteja avisado de que este tópico leva meus alunos alguns meses para finalmente entender. Você pode encontrar mais informações no capítulo 2 do livro Estruturas de dados e algoritmos em Java .

Não há procedimento mecânico que possa ser usado para obter o BigOh.

Como um "livro de receitas", para obter o BigOh a partir de um pedaço de código, primeiro você precisa perceber que está criando uma fórmula matemática para contar quantas etapas dos cálculos são executadas, com uma entrada de algum tamanho.

O objetivo é simples: comparar algoritmos do ponto de vista teórico, sem a necessidade de executar o código. Quanto menor o número de etapas, mais rápido o algoritmo.

Por exemplo, digamos que você tenha este pedaço de código:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

Essa função retorna a soma de todos os elementos da matriz e queremos criar uma fórmula para contar a complexidade computacional dessa função:

Number_Of_Steps = f(N)

Portanto, temos f(N)uma função para contar o número de etapas computacionais. A entrada da função é o tamanho da estrutura a processar. Isso significa que essa função é chamada como:

Number_Of_Steps = f(data.length)

O parâmetro Naceita o data.lengthvalor Agora precisamos da definição real da função f(). Isso é feito a partir do código fonte, no qual cada linha interessante é numerada de 1 a 4.

Existem muitas maneiras de calcular o BigOh. A partir deste ponto, assumiremos que toda sentença que não depende do tamanho dos dados de entrada executa um Cnúmero constante de etapas computacionais.

Vamos adicionar o número individual de etapas da função e nem a declaração da variável local nem a declaração de retorno dependem do tamanho da datamatriz.

Isso significa que as linhas 1 e 4 executam C uma quantidade de etapas cada, e a função é mais ou menos assim:

f(N) = C + ??? + C

A próxima parte é definir o valor da fordeclaração. Lembre-se de que estamos contando o número de etapas computacionais, o que significa que o corpo da forinstrução é executado Nvezes. Isso é o mesmo que adicionar C, Nvezes:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

Não existe uma regra mecânica para contar quantas vezes o corpo do foré executado, você precisa contar olhando o que o código faz. Para simplificar os cálculos, estamos ignorando as partes de inicialização, condição e incremento da variável for.

Para obter o BigOh real, precisamos da análise assintótica da função. Isso é feito da seguinte maneira:

1. Tire todas as constantes C.
2. De f()obter o polinômio na sua standard form.
3. Divida os termos do polinômio e ordene-os pela taxa de crescimento.
4. Mantenha o que cresce quando se Naproxima infinity.

Nosso f()tem dois termos:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Tirando todas as Cconstantes e partes redundantes:

f(N) = 1 + N ^ 1

Como o último termo é aquele que cresce quando se f()aproxima do infinito (pense nos limites ), esse é o argumento BigOh, e a sum()função possui um BigOh de:

O(N)

Existem alguns truques para resolver alguns complicados: use resumos sempre que puder.

Como exemplo, esse código pode ser facilmente resolvido usando somatórios:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

A primeira coisa que você precisa ser solicitado é a ordem de execução do foo(). Enquanto o habitual é ser O(1), você precisa perguntar a seus professores. O(1)significa (quase, principalmente) constante C, independente do tamanho N.

A forafirmação da frase número um é complicada. Enquanto o índice termina em 2 * N, o incremento é feito por dois. Isso significa que o primeiro foré executado apenas em Netapas, e precisamos dividir a contagem por dois.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

A frase número dois é ainda mais complicada, pois depende do valor de i. Dê uma olhada: o índice i pega os valores: 0, 2, 4, 6, 8, ..., 2 * N e o segundo foré executado: N vezes o primeiro, N - 2 o segundo, N - 4 o terceiro ... até o estágio N / 2, no qual o segundo fornunca é executado.

Na fórmula, isso significa:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Novamente, estamos contando o número de etapas . E, por definição, todo somatório deve sempre começar em um e terminar em um número maior ou igual a um.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Estamos assumindo que foo()é O(1)e toma Cmedidas.)

Temos um problema aqui: quando ileva o valor N / 2 + 1para cima, a soma interna termina em um número negativo! Isso é impossível e errado. Precisamos dividir o somatório em dois, sendo o ponto crucial que o momento ileva N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Desde o momento crucial i > N / 2, o interior fornão será executado, e estamos assumindo uma constante complexidade de execução C em seu corpo.

Agora as somas podem ser simplificadas usando algumas regras de identidade:

1. Soma (w de 1 a N) (C) = N * C
2. Somatório (w de 1 a N) (A (+/-) B) = Somatório (w de 1 a N) (A) (+/-) Somatório (w de 1 a N) (B)
3. Somatório (w de 1 a N) (w * C) = C * Somatório (w de 1 a N) (w) (C é uma constante, independente de w)
4. Somatório (w de 1 a N) (w) = (N * (N + 1)) / 2

Aplicando alguma álgebra:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

E o BigOh é:

O(N²)

Big O fornece o limite superior para a complexidade temporal de um algoritmo. Geralmente é usado em conjunto com o processamento de conjuntos de dados (listas), mas pode ser usado em outro lugar.

Alguns exemplos de como é usado no código C.

Digamos que temos uma matriz de n elementos

int array[n];

Se quiséssemos acessar o primeiro elemento da matriz, seria O (1), pois não importa o tamanho da matriz, sempre leva o mesmo tempo constante para obter o primeiro item.

x = array[0];

Se quisermos encontrar um número na lista:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

Isso seria O (n), já que no máximo teríamos que examinar a lista inteira para encontrar nosso número. O Big-O ainda é O (n), embora possamos encontrar nosso número na primeira tentativa e executar o loop uma vez porque o Big-O descreve o limite superior de um algoritmo (ômega é para limite inferior e teta é para limite restrito) .

Quando chegamos a loops aninhados:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Este é O (n ^ 2), pois para cada passagem do loop externo (O (n)) temos que percorrer toda a lista novamente para que os n se multipliquem, deixando-nos com n ao quadrado.

Isso mal arranha a superfície, mas quando você começa a analisar algoritmos mais complexos, matemática complexa envolvendo provas entra em jogo. Espero que isso familiarize você com o básico, pelo menos.

Embora seja útil saber como descobrir o tempo grande para o seu problema específico, conhecer alguns casos gerais pode ajudar bastante a tomar decisões em seu algoritmo.

Aqui estão alguns dos casos mais comuns, extraídos de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1) - Determinando se um número é par ou ímpar; usando uma tabela de pesquisa de tamanho constante ou tabela de hash

O (logn) - Localizando um item em uma matriz classificada com uma pesquisa binária

O (n) - Localizando um item em uma lista não classificada; adicionando dois números de n dígitos

O (n ² ) - Multiplicar dois números de n dígitos por um algoritmo simples; adicionando duas matrizes n × n; classificação por bolha ou inserção

O (n ³ ) - Multiplicando duas matrizes n × n por algoritmo simples

O (c ⁿ ) - Encontrar a solução (exata) para o problema do vendedor ambulante usando programação dinâmica; determinar se duas instruções lógicas são equivalentes usando força bruta

O (n!) - Resolvendo o problema do vendedor ambulante por meio da pesquisa de força bruta

O (n ⁿ ) - frequentemente usado em vez de O (n!) Para derivar fórmulas mais simples para complexidade assintótica

Lembrete pequeno: a big Onotação é usada para denotar complexidade assintótica (ou seja, quando o tamanho do problema cresce até o infinito) e oculta uma constante.

Isso significa que entre um algoritmo em O (n) e um em O (n ² ), o mais rápido nem sempre é o primeiro (embora exista sempre um valor de n tal que, para problemas de tamanho> n, o primeiro algoritmo seja o mais rápido).

Note que a constante oculta depende muito da implementação!

Além disso, em alguns casos, o tempo de execução não é uma função determinística do tamanho n da entrada. Faça a classificação usando a classificação rápida, por exemplo: o tempo necessário para classificar uma matriz de n elementos não é uma constante, mas depende da configuração inicial da matriz.

Existem diferentes complexidades de tempo:

• Pior caso (geralmente o mais simples de entender, embora nem sempre seja muito significativo)

• Caso médio (geralmente muito mais difícil de descobrir ...)

• ...

Uma boa introdução é Uma Introdução à Análise de Algoritmos, de R. Sedgewick e P. Flajolet.

Como você diz, premature optimisation is the root of all evile (se possível) a criação de perfis sempre deve ser usada ao otimizar o código. Pode até ajudá-lo a determinar a complexidade de seus algoritmos.

Vendo as respostas aqui, acho que podemos concluir que a maioria de nós realmente aproxima a ordem do algoritmo olhando -o e usando o bom senso em vez de calculá-lo com, por exemplo, o método mestre, como pensávamos na universidade. Com isso dito, devo acrescentar que até o professor nos incentivou (mais tarde) a pensar sobre isso em vez de apenas calculá-lo.

Também gostaria de adicionar como isso é feito para funções recursivas :

suponha que tenhamos uma função como ( código do esquema ):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

que calcula recursivamente o fatorial do número fornecido.

O primeiro passo é tentar determinar a característica de desempenho para o corpo da função apenas neste caso, nada de especial é feito no corpo, apenas uma multiplicação (ou o retorno do valor 1).

Portanto, o desempenho para o corpo é: O (1) (constante).

Em seguida, tente e determine isso para o número de chamadas recursivas . Nesse caso, temos n-1 chamadas recursivas.

Portanto, o desempenho das chamadas recursivas é: O (n-1) (a ordem é n, pois jogamos fora as partes insignificantes).

Em seguida, junte esses dois e você terá o desempenho para toda a função recursiva:

1 * (n-1) = O (n)

Peter , para responder às suas questões levantadas; o método que descrevo aqui realmente lida com isso muito bem. Mas lembre-se de que isso ainda é uma aproximação e não uma resposta matematicamente correta. O método descrito aqui também é um dos métodos que aprendemos na universidade e, se bem me lembro, foi usado para algoritmos muito mais avançados do que o fatorial que usei neste exemplo.
É claro que tudo depende de quão bem você pode estimar o tempo de execução do corpo da função e o número de chamadas recursivas, mas isso é verdade para os outros métodos.

Se o seu custo for um polinômio, mantenha o prazo mais alto, sem o multiplicador. Por exemplo:

O ((N / 2 + 1) * (n / 2)) = O (n ² /4 + n / 2) = O (n ² /4) = O (n ² )

Isso não funciona para séries infinitas, veja bem. Não existe uma receita única para o caso geral, embora em alguns casos comuns sejam aplicadas as seguintes desigualdades:

O (log N ) <O ( N ) <O ( N log N ) <O ( N ² ) <O ( N ^k ) <O (e ⁿ ) <O ( n !)

Eu penso sobre isso em termos de informação. Qualquer problema consiste em aprender um certo número de bits.

Sua ferramenta básica é o conceito de pontos de decisão e sua entropia. A entropia de um ponto de decisão é a informação média que ele fornecerá. Por exemplo, se um programa contém um ponto de decisão com duas ramificações, sua entropia é a soma da probabilidade de cada ramificação vezes o log ₂ da probabilidade inversa dessa ramificação. É o quanto você aprende executando essa decisão.

Por exemplo, uma ifinstrução com duas ramificações, ambas igualmente prováveis, tem uma entropia de 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Portanto, sua entropia é de 1 bit.

Suponha que você esteja pesquisando uma tabela de N itens, como N = 1024. Esse é um problema de 10 bits porque log (1024) = 10 bits. Portanto, se você puder pesquisá-lo com instruções IF com resultados igualmente prováveis, deve tomar 10 decisões.

É o que você obtém com a pesquisa binária.

Suponha que você esteja fazendo uma pesquisa linear. Você olha para o primeiro elemento e pergunta se é o que deseja. As probabilidades são 1/1024, e 1023/1024, não. A entropia dessa decisão é 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * cerca de 0 = cerca de 0,01 bits. Você aprendeu muito pouco! A segunda decisão não é muito melhor. É por isso que a pesquisa linear é tão lenta. De fato, é exponencial o número de bits que você precisa aprender.

Suponha que você esteja fazendo indexação. Suponha que a tabela seja pré-classificada em vários compartimentos e você use alguns dos bits da chave para indexar diretamente para a entrada da tabela. Se houver 1024 posições, a entropia será 1/1024 * log (1024) + 1/1024 * log (1024) + ... para todos os 1024 resultados possíveis. Isso é 1/1024 * 10 vezes 1024 resultados ou 10 bits de entropia para essa operação de indexação. É por isso que a pesquisa de indexação é rápida.

Agora pense em classificação. Você tem N itens e uma lista. Para cada item, você precisa procurar para onde o item está na lista e adicioná-lo à lista. Portanto, a classificação leva aproximadamente N vezes o número de etapas da pesquisa subjacente.

Portanto, tipos baseados em decisões binárias com resultados aproximadamente igualmente prováveis ​​tomam todas as etapas O (N log N). Um algoritmo de classificação O (N) é possível se for baseado na pesquisa de indexação.

Descobri que quase todos os problemas de desempenho algorítmico podem ser analisados ​​dessa maneira.

Vamos começar do começo.

Antes de tudo, aceite o princípio de que certas operações simples nos dados podem ser feitas no O(1)tempo, ou seja, no tempo independente do tamanho da entrada. Essas operações primitivas em C consistem em

1. Operações aritméticas (por exemplo, + ou%).
2. Operações lógicas (por exemplo, &&).
3. Operações de comparação (por exemplo, <=).
4. Estruture as operações de acesso (por exemplo, indexação de array como A [i] ou ponteiro a seguir ao operador ->).
5. Atribuição simples, como copiar um valor em uma variável.
6. Chamadas para funções de biblioteca (por exemplo, scanf, printf).

A justificativa para esse princípio requer um estudo detalhado das instruções da máquina (etapas primitivas) de um computador típico. Cada uma das operações descritas pode ser realizada com um pequeno número de instruções da máquina; geralmente apenas uma ou duas instruções são necessárias. Como conseqüência, vários tipos de instruções em C podem ser executados no O(1)tempo, ou seja, em uma quantidade constante de tempo, independentemente da entrada. Estes simples incluem

1. Instruções de atribuição que não envolvem chamadas de função em suas expressões.
2. Leia as declarações.
3. Escreva instruções que não exijam chamadas de função para avaliar argumentos.
4. As instruções de salto quebram, continuam, vão e retornam a expressão, onde a expressão não contém uma chamada de função.

Em C, muitos for-loops são formados ao inicializar uma variável de índice com algum valor e incrementar essa variável em 1 a cada vez que o loop é executado. O loop for termina quando o índice atinge algum limite. Por exemplo, o loop for

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

usa a variável de índice i. Ele incrementa i em 1 a cada vez que o loop é repetido, e as iterações param quando eu alcança n - 1.

No entanto, no momento, concentre-se na forma simples de loop for, onde a diferença entre os valores final e inicial, dividida pela quantidade pela qual a variável de índice é incrementada nos diz quantas vezes percorremos o loop . Essa contagem é exata, a menos que haja maneiras de sair do loop por meio de uma instrução de salto; é um limite superior no número de iterações em qualquer caso.

Por exemplo, o loop for itera ((n − 1) − 0)/1 = n − 1 times, uma vez que 0 é o valor inicial de i, n - 1 é o valor mais alto atingido por i (ou seja, quando eu alcança n-1, o loop para e nenhuma iteração ocorre com i = n− 1) e 1 são adicionados a i em cada iteração do loop.

No caso mais simples, onde o tempo gasto no corpo do loop é o mesmo para cada iteração, podemos multiplicar o limite superior do oh pelo número de vezes ao redor do loop . A rigor, devemos adicionar tempo O (1) para inicializar o índice do loop e tempo O (1) para a primeira comparação do índice do loop com o limite , porque testamos mais uma vez do que percorremos o loop. No entanto, a menos que seja possível executar o loop zero vezes, o tempo para inicializar o loop e testar o limite uma vez é um termo de ordem inferior que pode ser descartado pela regra de soma.

Agora considere este exemplo:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Sabemos que a linha (1) leva O(1)tempo. Claramente, contornamos o loop n vezes, como podemos determinar subtraindo o limite inferior do limite superior encontrado na linha (1) e adicionando 1. Como o corpo, a linha (2) leva o tempo O (1), podemos negligenciar o tempo para incrementar j e o tempo para comparar j com n, os quais também são O (1). Assim, o tempo de execução das linhas (1) e (2) é o produto de n e O (1) , que é O(n).

Da mesma forma, podemos limitar o tempo de execução do loop externo que consiste nas linhas (2) a (4), que é

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Já estabelecemos que o loop das linhas (3) e (4) leva tempo O (n). Assim, podemos negligenciar o tempo O (1) para incrementar i e testar se i <n em cada iteração, concluindo que cada iteração do loop externo leva tempo O (n).

A inicialização i = 0 do loop externo e o teste (n + 1) da condição i <n também levam tempo O (1) e podem ser negligenciados. Finalmente, observamos que percorremos o loop externo n vezes, levando O (n) para cada iteração, fornecendo um O(n^2)tempo total de execução.

Um exemplo mais prático.

Se você deseja estimar a ordem do seu código empiricamente, em vez de analisá-lo, você pode manter uma série de valores crescentes de n e cronometrar seu código. Plote seus horários em uma escala de log. Se o código for O (x ^ n), os valores deverão cair em uma linha de inclinação n.

Isso tem várias vantagens em apenas estudar o código. Por um lado, você pode ver se está no intervalo em que o tempo de execução se aproxima de sua ordem assintótica. Além disso, você pode achar que algum código que você pensou que fosse da ordem O (x) é realmente da ordem O (x ^ 2), por exemplo, devido ao tempo gasto nas chamadas da biblioteca.

Basicamente, o que aparece 90% do tempo é apenas analisar loops. Você tem loops simples, duplos e triplos aninhados? Você tem O (n), O (n ^ 2), O (n ^ 3) tempo de execução.

Muito raramente (a menos que você esteja escrevendo uma plataforma com uma extensa biblioteca base (como, por exemplo, o .NET BCL ou o STL do C ++), encontrará algo mais difícil do que apenas olhar seus loops (para obter instruções, while, goto, etc ...)

A notação Big O é útil porque é fácil trabalhar e oculta complicações e detalhes desnecessários (para algumas definições de desnecessário). Uma boa maneira de descobrir a complexidade dos algoritmos de dividir e conquistar é o método de árvore. Digamos que você tenha uma versão do quicksort com o procedimento mediano, portanto divida a matriz em sub-arrays perfeitamente equilibrados todas as vezes.

Agora construa uma árvore correspondente a todas as matrizes com as quais você trabalha. Na raiz, você tem a matriz original, a raiz tem dois filhos, que são os sub-arranjos. Repita isso até ter matrizes de elemento único na parte inferior.

Como podemos encontrar a mediana no tempo O (n) e dividir a matriz em duas partes no tempo O (n), o trabalho realizado em cada nó é O (k), onde k é o tamanho da matriz. Cada nível da árvore contém (no máximo) toda a matriz, de modo que o trabalho por nível é O (n) (os tamanhos das sub-matrizes somam n, e como temos O (k) por nível, podemos adicionar isso) . Existem apenas níveis de log (n) na árvore, pois cada vez que reduzimos a entrada pela metade.

Portanto, podemos limitar a quantidade de trabalho por O (n * log (n)).

No entanto, o Big O esconde alguns detalhes que às vezes não podemos ignorar. Considere calcular a sequência de Fibonacci com

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

e vamos apenas assumir que a e b são BigIntegers em Java ou algo que pode lidar com números arbitrariamente grandes. A maioria das pessoas diria que este é um algoritmo O (n) sem vacilar. O raciocínio é que você possui n iterações no loop for e O (1) trabalha ao lado do loop.

Mas os números de Fibonacci são grandes, o n-ésimo número de Fibonacci é exponencial em n; portanto, apenas o armazenamento será da ordem de n bytes. Realizar adição com números inteiros grandes exigirá O (n) quantidade de trabalho. Portanto, a quantidade total de trabalho realizado neste procedimento é

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

Portanto, esse algoritmo é executado em tempo quadrádico!

Em geral, menos útil, eu acho, mas por uma questão de completude, há também um Big Omega Ω , que define um limite inferior da complexidade de um algoritmo, e um Big Theta Θ , que define um limite superior e inferior.

Divida o algoritmo em partes que você conhece a grande notação O e combine através de grandes operadores O. Essa é a única maneira que eu conheço.

Para mais informações, consulte a página da Wikipedia sobre o assunto.

Familiaridade com os algoritmos / estruturas de dados que eu uso e / ou análise rápida do aninhamento de iterações. A dificuldade é quando você chama uma função de biblioteca, possivelmente várias vezes - muitas vezes você pode não ter certeza se está chamando a função desnecessariamente às vezes ou qual implementação elas estão usando. Talvez as funções da biblioteca devam ter uma medida de complexidade / eficiência, seja Big O ou outra métrica, disponível na documentação ou mesmo no IntelliSense .

Quanto a "como você calcula" Big O, isso faz parte da teoria da complexidade computacional . Para alguns casos (muitos) especiais, você pode vir com algumas heurísticas simples (como multiplicar contagens de loop para loops aninhados), esp. quando tudo o que você quer é uma estimativa do limite superior e você não se importa se for muito pessimista - o que eu acho que é provavelmente o que sua pergunta se refere.

Se você realmente deseja responder à sua pergunta para qualquer algoritmo, o melhor que pode fazer é aplicar a teoria. Além da análise simplista do "pior caso", achei a análise amortizada muito útil na prática.

Para o 1º caso, o loop interno é executado n-ivezes, portanto, o número total de execuções é a soma da ipassagem de 0para n-1(porque menor que, não menor que ou igual) da n-i. Você finalmente n*(n + 1) / 2, entãoO(n²/2) = O(n²) .

Para o segundo loop, iestá entre 0e nincluído no loop externo; então o loop interno é executado quando jfor estritamente maior que n, o que é impossível.

Além de usar o método master (ou uma de suas especializações), testo meus algoritmos experimentalmente. Isso não pode provar que uma classe de complexidade específica é alcançada, mas pode garantir que a análise matemática é apropriada. Para ajudar com essa garantia, uso ferramentas de cobertura de código em conjunto com meus experimentos, para garantir que estou exercitando todos os casos.

Como um exemplo muito simples, diga que você queria fazer uma verificação de integridade na velocidade da classificação da lista do .NET Framework. Você pode escrever algo como o seguinte e analisar os resultados no Excel para garantir que eles não excedam uma curva n * log (n).

Neste exemplo, medo o número de comparações, mas também é prudente examinar o tempo real necessário para cada tamanho de amostra. No entanto, você deve ter ainda mais cuidado ao medir o algoritmo e não incluir artefatos da sua infraestrutura de teste.

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

Não se esqueça de permitir também complexidades de espaço que também podem ser motivo de preocupação se houver recursos limitados de memória. Então, por exemplo, você pode ouvir alguém querendo um algoritmo de espaço constante, que é basicamente uma maneira de dizer que a quantidade de espaço ocupada pelo algoritmo não depende de nenhum fator dentro do código.

Às vezes, a complexidade pode vir de quantas vezes é chamado algo, com que freqüência um loop é executado, com que freqüência a memória é alocada e assim por diante, é outra parte para responder a essa pergunta.

Por fim, o grande O pode ser usado para os piores casos, os melhores casos e os casos de amortização, onde geralmente é o pior caso usado para descrever o quão ruim um algoritmo pode ser.

O que geralmente é esquecido é o comportamento esperado dos seus algoritmos. Ele não altera o Big-O do seu algoritmo , mas está relacionado à declaração "otimização prematura ..."

O comportamento esperado do seu algoritmo é - muito confuso - com que rapidez você pode esperar que seu algoritmo trabalhe com dados que provavelmente verá.

Por exemplo, se você está procurando um valor em uma lista, é O (n), mas se você sabe que a maioria das listas que você vê tem seu valor antecipadamente, o comportamento típico do seu algoritmo é mais rápido.

Para realmente defini-lo, você precisa ser capaz de descrever a distribuição de probabilidade do seu "espaço de entrada" (se precisar classificar uma lista, com que frequência essa lista já será classificada? Com ​​que frequência é totalmente revertida? Como geralmente é classificada principalmente?) Nem sempre é possível que você saiba disso, mas às vezes sabe.

ótima pergunta!

Isenção de responsabilidade: esta resposta contém declarações falsas, veja os comentários abaixo.

Se você estiver usando o Big O, estará falando do pior caso (mais sobre o que isso significa mais tarde). Além disso, há teta capital para o caso médio e um grande ômega para o melhor caso.

Confira este site para uma definição formal adorável de Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) significa que existem constantes positivas c e k, de modo que 0 ≤ f (n) ≤ cg (n) para todos os n ≥ k. Os valores de c e k devem ser fixos para a função f e não devem depender de n.

Ok, agora o que queremos dizer com complexidades de "melhor ou pior" caso?

Isto é provavelmente mais claramente ilustrado através de exemplos. Por exemplo, se estivermos usando a pesquisa linear para encontrar um número em uma matriz classificada, o pior caso é quando decidimos procurar o último elemento da matriz, pois isso levaria tantas etapas quanto os itens da matriz. O melhor caso seria quando procurarmos o primeiro elemento uma vez que concluiríamos após a primeira verificação.

O objetivo de todas essas complexidades de adjetivo- case é que estamos procurando uma maneira de representar graficamente a quantidade de tempo que um programa hipotético é executado em termos de tamanho de variáveis ​​específicas. No entanto, para muitos algoritmos, você pode argumentar que não há um tempo único para um tamanho específico de entrada. Observe que isso contradiz o requisito fundamental de uma função, qualquer entrada não deve ter mais que uma saída. Então, criamos várias funções para descrever a complexidade de um algoritmo. Agora, mesmo que a busca em uma matriz de tamanho n possa levar uma quantidade variável de tempo, dependendo do que você está procurando na matriz e dependendo proporcionalmente a n, podemos criar uma descrição informativa do algoritmo usando o melhor caso, o caso médio e classes de pior caso.

Desculpe, isso é tão mal escrito e falta muita informação técnica. Mas espero que isso facilite a reflexão sobre as classes de complexidade de tempo. Depois que você se familiariza com isso, torna-se uma simples questão de analisar seu programa e procurar itens como forops, que dependem do tamanho e do raciocínio da matriz com base nas estruturas de dados, que tipo de entrada resultaria em casos triviais e que entrada resultaria nos piores casos.

Eu não sei como resolver isso programaticamente, mas a primeira coisa que as pessoas fazem é que amostremos o algoritmo para certos padrões no número de operações realizadas, digamos 4n ^ 2 + 2n + 1, temos 2 regras:

1. Se tivermos uma soma de termos, o termo com a maior taxa de crescimento é mantido, com outros termos omitidos.
   
2. Se temos um produto de vários fatores, fatores constantes são omitidos.

Se simplificarmos f (x), onde f (x) é a fórmula para o número de operações realizadas (4n ^ 2 + 2n + 1 explicado acima), obteremos o valor de O grande [O (n ^ 2) neste caso]. Mas isso teria que explicar a interpolação de Lagrange no programa, que pode ser difícil de implementar. E se o valor real de O grande fosse O (2 ^ n), e pudéssemos ter algo como O (x ^ n), então esse algoritmo provavelmente não seria programável. Mas se alguém me provar errado, me dê o código. . . .

Para o código A, o loop externo será executado por n+1tempos, o tempo '1' significa o processo que verifica se eu ainda atende ao requisito. E o loop interno executa ntempos, n-2tempos .... Assim 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²),.

Para o código B, embora o loop interno não intervenha e execute foo (), o loop interno será executado por n vezes, dependendo do tempo de execução do loop externo, que é O (n)

Eu gostaria de explicar o Big-O em um aspecto um pouco diferente.

O Big-O serve apenas para comparar a complexidade dos programas, o que significa com que rapidez eles crescem quando os insumos estão aumentando e não o tempo exato gasto para executar a ação.

IMHO nas fórmulas big-O, é melhor você não usar equações mais complexas (você pode apenas seguir as do gráfico a seguir). No entanto, você ainda pode usar outra fórmula mais precisa (como 3 ^ n, n ^ 3, .. .) mas, mais do que isso, às vezes pode ser enganador! É melhor mantê-lo o mais simples possível.

Gostaria de enfatizar mais uma vez que aqui não queremos obter uma fórmula exata para o nosso algoritmo. Queremos apenas mostrar como cresce quando as entradas estão crescendo e comparar com os outros algoritmos nesse sentido. Caso contrário, é melhor usar métodos diferentes, como marcação de banco de dados.