Big O, como calcular/aproximá-la?

https://stackoverflow.com/questions/3255

08-06-2019
|

Pergunta

A maioria das pessoas com um grau no CS, certamente, sabe o que Grande S representa.Ajuda-nos para medir o grau de (in)eficiente de um algoritmo é realmente, e, se você souber em que categoria o problema que você está tentando resolver estabelece em você pode descobrir se ainda é possível espremer pouco mais de desempenho.¹

Mas estou curiosa, como fazer você calcular ou aproximar a complexidade de seus algoritmos?

¹ _{mas como dizem, não exagere, prematura de otimização é a raiz de todo o mal, e otimização sem causa justificada, deve merecer esse nome.}

Solução

Eu vou fazer o meu melhor para explicá-la aqui em termos mais simples, mas esteja avisado que este tema leva os meus alunos um par de meses para finalmente entender.Você pode encontrar mais informações no Capítulo 2 do Estruturas de dados e Algoritmos em Java livro.

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

Como um "livro de receitas", para obter o BigOh a partir de um pedaço de código que você primeiro precisa perceber que você está criando uma fórmula matemática para contar quantos passos de cálculos são executados dada uma entrada de tamanho de alguns.

O objectivo é simples:para comparar os algoritmos a partir de um ponto de vista teórico, sem a necessidade de executar o código.O menor número de passos, o 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
}

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

Number_Of_Steps = f(N)

Assim, temos f(N), uma função para contar o número de tais etapas.A entrada da função é o tamanho da estrutura e o processo.Isso significa que esta função é chamada, tais como:

Number_Of_Steps = f(data.length)

O parâmetro N leva a data.length o valor.Agora temos a real definição da função f().Isso é feito a partir do código-fonte, em que cada uma interessante linha é numerada de 1 a 4.

Há muitas maneiras de se calcular o BigOh.A partir deste ponto para a frente vamos assumir que cada frase que não dependem do tamanho da entrada de dados é uma constante C número computacional passos.

Estamos indo para adicionar o número individual de etapas da função, e nem a declaração de variável local nem a instrução de retorno depende do tamanho do data matriz.

O que significa que as linhas 1 e 4 C quantidade de etapas cada, e a função é semelhante a esse:

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

A parte seguinte é para definir o valor da for instrução.Lembre-se que estamos a contar o número de tais etapas, o que significa que o corpo da for instrução é executada N vezes.Isso é o mesmo que adicionar C, N horários:

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

Não há mecânica regra para contagem de quantas vezes o corpo do for é executado, você precisa contar ao ver o que o código faz.Para simplificar os cálculos, estamos a ignorar a variável de inicialização, condição e incremento de partes do for instrução.

Para obter o real BigOh precisamos da Análise assintótica da função.Este é mais ou menos feito como este:

Tire todas as constantes C.
A partir de f() obter o polynomium em sua standard form.
Divida os termos da polynomium e ordenar a taxa de crescimento.
Manter o que cresce quando N abordagens infinity.

Nossa f() tem dois termos:

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

Tirando todas as C constantes e partes redundantes:

f(N) = 1 + N ^ 1

Desde o último termo é a que cresce quando f() se aproxima de infinito (acho que no limites esta é a BigOh argumento, e o sum() a função tem um BigOh de:

O(N)

Existem alguns truques para resolver algumas rasteiras:utilização os somatórios sempre que você pode.

Como um exemplo, este código pode ser facilmente resolvido usando os somatórios:

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

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

O for declaração sobre a frase número um é complicado.Enquanto o índice termina em 2 * N, o aumento é feito por dois.O que significa que o primeiro for é executado apenas N passos, e precisamos dividir a contagem de dois.

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

A frase número dois é ainda mais complicado, pois depende do valor da i.Dê uma olhada:o índice i assume os valores:0, 2, 4, 6, 8, ..., 2 * N, e a segunda for executado:N vezes o primeiro, N - 2, a segunda, N - 4, o terceiro...até N / 2 fase, em que o segundo for nunca é executado.

Na fórmula, o que significa que:

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

Novamente, estamos a contar o número de passos.E, por definição, todos somatī orio deve sempre começar em uma, 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 supondo que foo() é O(1) e leva C passos.)

Temos um problema aqui:quando i toma o valor N / 2 + 1 para cima, o interior da Soma termina em um número negativo!Isso é impossível e errado.Nós precisamos dividir a soma em dois, sendo o ponto crucial o momento i leva 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 decisivo i > N / 2, o interior for não executado, e nós estamos supondo uma constante C execução a complexidade em seu corpo.

Agora o somatī orios pode ser simplificada usando algumas regras de identidade:

Soma(w de 1 a N)( C ) = N * C
Soma(w de 1 a N)( A (+/-) B ) = Soma(w de 1 a N)( A ) (+/-) Soma(w de 1 a N)( B )
Soma(w de 1 a N)( w * C ) = C * Soma(w de 1 a N)( w ) (C é uma constante, independente da w)
Soma(w de 1 a N)( w ) = (N * (N + 1)) / 2

Aplicando um pouco de á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²)

Outras dicas

Big O, dá o limite superior para o tempo de complexidade de um algoritmo.É normalmente usado em conjunto com o processamento de conjuntos de dados (listas), mas pode ser usado em outro lugar.

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

Dizer que temos um vetor de n elementos

int array[n];

Se quisermos acessar o primeiro elemento do array, este seria O(1), pois não importa o quão grande é a matriz, ele toma sempre a mesma constante de tempo 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; }
}

Este seria O(n), pois, no máximo, teríamos de olhar através de toda a lista para encontrar o nosso número.O Grande-O ainda é O(n), mesmo que possamos encontrar a nossa primeira tentativa e executar o loop uma vez porque Grande-Ó descreve o limite superior de um algoritmo (omega é para o limite inferior e theta é para tight dependente).

Quando chegamos ao loops aninhados:

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

Este é O(n^2) pois, a cada passagem do loop externo ( S(n) ) temos que percorrer toda a lista novamente, de modo a n multiplicar deixando-nos com n quadrados.

Este é apenas arranhando a superfície, mas quando você começa a analisar algoritmos mais complexos complexos envolvendo provas entra em jogo.Espero que este familiariza-lo com o básico, pelo menos, embora.

Enquanto saber como descobrir o Grande, O tempo para o seu problema particular, é útil conhecer alguns casos gerais pode ir um longo caminho para ajudar você a tomar decisões em seu algoritmo.

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

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

O(logn) - para Encontrar um item em um array ordenado com um binário de pesquisa

S(n) - Encontrar um item em uma lista não-ordenada;a adição de dois n-números de dígitos

O(n²) - Multiplicando os dois n-números de dígitos por um algoritmo simples;a adição de dois n×n matrizes;classificação de bolha ou de inserção de classificação

O(n³) - Multiplicando os dois n×n matrizes pelo algoritmo simples

O(cⁿ) - Localizar o (exata) a solução para o problema do caixeiro viajante usando programação dinâmica;determinar se duas expressões lógicas são equivalentes utilizando a força bruta

O(n!) - Resolver o problema do caixeiro viajante através de pesquisa de força bruta

O(nⁿ Muitas vezes utilizado em vez de S(n!) para derivar fórmulas mais simples para a complexidade assintótica

Pequeno lembrete:o big O a notação é usada para denotar o assimptótico complexidade (isto é, quando o tamanho do problema cresce para infinito), e ela esconde uma constante.

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

Observe que o oculto constante depende muito da aplicação!

Também, em alguns casos, o tempo de execução não é uma função determinística do tamanho n da entrada.Levam a separação usando o quick sort, por exemplo:o tempo necessário para ordenar um vetor 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 muito significativo)
Caso médio (geralmente muito mais difícil de descobrir...)
...

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

Como você diz, premature optimisation is the root of all evil, e (se possível) criação de perfis realmente deve ser usado sempre, ao otimizar o código.Ele pode até ajudar a determinar a complexidade de seus algoritmos.

Vendo as respostas aqui eu acho que podemos concluir que a maioria de nós, de fato, aproximar o fim do algoritmo procura ele e use o senso comum, em vez de calculá-lo com, por exemplo, o método mestre como estávamos pensamento na universidade.Com o que disse, devo acrescentar que, mesmo o professor encorajou-nos (mais tarde) realmente acho que sobre isso, em vez de apenas calculá-la.

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

suponha que temos uma função do tipo (esquema de código):

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

que calcula recursivamente o fatorial de um número dado.

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

De modo que o o desempenho do corpo é:O(1) (constante).

Em seguida, experimente e determinar isso para o número de chamadas recursivas.Neste caso, temos n-1 chamadas recursivas.

De modo que o o desempenho para as chamadas recursivas é:O(n-1) (a ordem é n, como nós jogamos fora o insignificante partes).

Em seguida, coloque os dois juntos e você terá o desempenho para toda função recursiva:

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

Pedro, para responder a seu levantou questões; o método que eu descrever aqui, na verdade, lida com isso muito bem.Mas tenha em mente que este ainda é um aproximação e não um completo matematicamente resposta correta.O método descrito aqui é também um dos métodos de nós foram ensinados na universidade, e se bem me lembro foi usado para muito mais avançados algoritmos de que o fatorial utilizado 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 que é tão verdadeiro para os outros métodos.

Se o custo for um polinˆ omio, basta manter a ordem mais elevada de prazo, sem o seu multiplicador.E. g.:

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

Isto não funciona para séries infinitas, você mente.Não há uma única receita para o caso geral, que para alguns casos comuns, as seguintes desigualdades aplicar:

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

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

Sua ferramenta básica é o conceito de pontos de decisão e a sua entropia.A entropia de um ponto de decisão é a média de informações que ele vai dar a você.Por exemplo, se um programa que contém um ponto de decisão, com dois ramos, é a entropia é a soma da probabilidade de cada ramo vezes o log₂ o inverso da probabilidade de que ramo.Isso é o quanto você aprendeu executar essa decisão.

Por exemplo, uma if declaração de ter dois ramos, 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, a sua entropia é de 1 bit.

Suponha que você está procurando um tabela de itens N, como N=1024.Que é a 10-bit problema porque o registo de(1024) = 10 bits.Então, se você pode pesquisa-lo com instruções SE que têm a mesma probabilidade de resultados, o que deve levar de 10 a tomada de decisões.

É isso que você ganha com pesquisa binária.

Suponha que você está fazendo pesquisa linear.Você olha para o primeiro elemento e pergunte se é o que você quer.As probabilidades são 1/1024 que ele é, e 1023/1024 que não é assim.A entropia de que a decisão é 1/1024*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * sobre 0 = sobre .01 pouco.Você aprendeu muito pouco!A segunda decisão não é muito melhor.É por isso que a pesquisa linear é muito lento.Na verdade, é exponencial no número de bits que você precisa aprender.

Suponha que você está fazendo de indexação.Suponha que a tabela é pré-classificados em um monte de lixo, e você pode usar algumas de todos os bits da chave de índice diretamente para a entrada da tabela.Se há 1024 bins, a entropia é 1/1024 * log(1024) + 1/1024 * log(1024) + ...para todos os 1024 resultados possíveis.Este é 1/1024 * 10 vezes 1024 resultados, ou 10 bits de entropia para que uma operação de indexação.É por isso que a indexação de pesquisa é rápida.

Agora pense sobre a classificação.Você tem N elementos, e você tem uma lista.Para cada item, você tem que pesquisar para onde o item passa na lista e, em seguida, adicioná-lo à lista.Assim, a classificação leva cerca de N vezes o número de etapas do subjacente de busca.

Então ordena com base em decisões binárias ter aproximadamente a mesma probabilidade de resultados de todos sobre O(N log N) passos.Um S(N) algoritmo de ordenação é possível se for baseada em indexação de pesquisa.

Descobri que quase todos os algoritmos de problemas de desempenho pode ser visto dessa forma.

Vamos começar desde o início.

Primeiro de tudo, aceitar o princípio de que certas operações simples sobre os dados pode ser feita em O(1) o tempo, que é, no tempo que é independente do tamanho da entrada.Estas operações primitivas em C consistem em

Operações aritméticas (e.g.+ ou %).
Operações lógicas (por exemplo, &&).
Operações de comparação (por exemplo, <=).
Estrutura de acesso operações (e.g.matriz de indexação como Um[i], ou o ponteiro fol- de descida com o -> operador).
Atribuição simples como copiar um valor para uma variável.
Chamadas para funções de biblioteca (por exemplo, scanf, printf).

A justificativa para este princípio requer um estudo detalhado de instruções de máquina (primitiva passos) de um computador típico.Cada uma das operações descritas pode ser feito com algumas pequeno número de instruções de máquina;muitas vezes apenas um ou dois são necessárias instruções.Como consequência, vários tipos de instruções em C pode ser executado em O(1) o tempo, que é, em algumas quantidade constante de tempo independente da entrada.Estes incluem

Instruções de atribuição que não envolvem chamadas de função em suas expressões.
Declarações de leitura.
Instruções de gravação que não necessitam de chamadas de função para avaliar argumentos.
O salto instruções break, continue, goto, e a expressão de retorno, onde a expressão não contém uma chamada de função.

Em C, para muitos loops são formadas por inicializar uma variável de índice para algum valor e o incremento da variável por 1 a cada vez que todo o ciclo.O ciclo termina quando o índice atinge algum limite.Por exemplo, o ciclo

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;
}

utiliza a variável de índice i.Ele incrementa i por 1 a cada vez que todo o ciclo, e as iterações parar quando chega a n − 1.

No entanto, para o momento, concentrar-se na simples forma de ciclo, onde o diferença entre a final e a inicial de valores, dividida pelo valor pelo qual a variável de índice é incrementado nos diz quantas vezes vamos ao redor do circuito.Que o conde é exata, a menos que há maneiras de sair do loop através de um salto de instrução;ele é um limite superior do número de iterações em qualquer caso.

Por exemplo, o ciclo repete-se ((n − 1) − 0)/1 = n − 1 times, uma vez que 0 é o valor inicial de i, n − 1 é o valor mais alto alcançado pelo eu (i.é., quando eu chega a n−1, o ciclo pára e nenhuma iteração ocorre com i = n−1), e 1 é adicionado para eu a cada iteração do loop.

No caso mais simples, onde o tempo gasto no corpo do loop é o mesmo para cada iteração, nós podemos multiplicar o big-oh limite superior para o corpo pelo número de de vezes em todo o ciclo.Estritamente falando, então temos que adicionar O(1) tempo para inicializar índice de loop e O(1) tempo para a primeira comparação do índice de loop com o limite de, porque nós testamos mais uma vez do que ir todo o ciclo.No entanto, a menos que é possível executar o loop zero vezes, o tempo para inicializar o loop de teste e o limite de uma só vez é uma ordem inferior termo que pode ser ignorados pelo somatório regra.

Agora, considere este exemplo:

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

Sabemos que linha (1) leva O(1) em tempo.Claramente, vamos ao redor do loop n vezes, como podemos determinar subtraindo-se o limite inferior da limite superior encontrado na linha (1) e, em seguida, a adição de 1.Desde que o corpo, a linha (2), leva O tempo(1), podemos negligenciar o tempo para incrementar j e o tempo para comparar j n, ambos os quais também são O(1).Assim, o tempo de execução das linhas (1) e (2) é o produto de n e S(1), o que é O(n).

Da mesma forma, podemos ligado o tempo de execução do loop externo consiste de 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 de linhas (3) e (4) leva O(n).Assim, podemos negligenciar o(1) hora de incrementar i e para testar se eu < n em a cada iteração, concluindo-se que a cada iteração do loop externo leva tempo O(n).

A inicialização i = 0 do loop externo e o (n + 1)st teste da condição eu < n da mesma forma, tomar O tempo(1) e pode ser negligenciada.Finalmente, observamos que vamos todo o loop externo n vezes, tendo O(n) para cada iteração, o que dá um total O(n^2) tempo de execução.

Mais um exemplo prático.

enter image description here

Se você deseja estimar a ordem de seu código de forma empírica, em vez de analisar o código, você poderia ficar em uma série de valores crescentes de n e o tempo de seu código.Enredo seus intervalos em uma escala log.Se o código é O(x^n), os valores devem cair sobre uma linha de inclinação n.

Isto tem várias vantagens sobre a apenas estudar o código.Para uma coisa, você pode ver se você está na faixa onde 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 era da ordem de O(x) é realmente ordem de O(x^2), por exemplo, por causa do tempo gasto em chamadas de biblioteca.

Basicamente a única coisa que as culturas de até 90% do tempo é apenas a análise de loops.Você tem único, duplo, triplo loops aninhados?O que você tem é de O(n), O(n^2), O(n^3) tempo de execução.

Muito raramente (menos que você está escrevendo uma plataforma com uma extensa biblioteca de base (como, por exemplo, o .NET BCL, ou C++STL) você vai encontrar tudo o que é mais difícil do que apenas olhar para o seu loops (para declarações, enquanto que, goto, etc...)

Quebrar o algoritmo em pedaços você sabe o big O notation, e combinar através grande O operadores.Essa é a única maneira que eu sei.

Para mais informações, verifique o A página da wikipédia sobre o assunto.

Big O notation é útil porque é fácil trabalhar com e esconde complicações desnecessárias e detalhes (para alguns definição do desnecessário).Uma boa maneira de trabalhar a complexidade de dividir e conquistar algoritmos é o método de árvore.Digamos que você tenha uma versão do quicksort com a mediana procedimento, assim você divide a matriz em perfeito equilíbrio subarrays de cada vez.

Agora construir uma árvore correspondente a todas as matrizes que trabalhar.Na raiz você tem a matriz original, a raiz tem dois filhos que são a subarrays.Repita isso até que você tenha único elemento de matrizes na parte inferior.

Desde que nós podemos encontrar a mediana em tempo O(n) e dividir a matriz em duas partes, em tempo O(n), o trabalho feito 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 é de O(n) (o tamanho do subarrays adicionar até n, e desde então temos S(k) por nível, podemos adicionar isso).Há apenas log(n) níveis na árvore, pois cada vez que metade de entrada.

Portanto, podemos limite superior da quantidade de trabalho por O(n*log(n)).

No entanto, Grande O esconde alguns detalhes que, às vezes, não se pode ignorar.Considere a possibilidade de computar a seqüência de Fibonacci com

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

e vamos assumir a e b são BigIntegers em Java ou algo que pode manipular arbitrariamente grande de números.A maioria das pessoas diria que este é um tempo O(n) algoritmo sem vacilar.O raciocínio é que você tem n iterações do loop for e O(1) o trabalho no lado do loop.

Mas os números de Fibonacci são grandes, o n-ésimo número de Fibonacci é exponencial em n então, basta armazenar o fim de n bytes.Realizar juntamente com inteiros grandes vai tirar O(n) quantidade de trabalho.Assim, a quantidade total de trabalho realizado neste procedimento é

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

Assim, este algoritmo é executado em quadradic tempo!

A familiaridade com os algoritmos/estruturas de dados eu uso e/ou rápida olhada análise de iteração de nidificação.A dificuldade é quando você chamar uma função de biblioteca, possivelmente, várias vezes - muitas vezes você pode não ter certeza se você está chamando a função desnecessariamente, às vezes, ou que a implementação que eles estão usando.Talvez funções de biblioteca deve ter uma complexidade/eficiência medida, se que ser Grande O ou alguma outra métrica, que está disponível na documentação ou até mesmo IntelliSense.

Menos útil em geral, eu acho, mas por uma questão de completude, há também um Grande Omega Ω, o que define uma menor ligados em um algoritmo de complexidade, e uma Grande Θ Teta, que define um limite superior e limite inferior.

Como para "como é calculado o" Big O, esta é a parte de A teoria da complexidade computacional.Para alguns (muitos) casos especiais, poderá ser capaz de vir com algumas simples heurísticas (como multiplicação loop conta para loops aninhados), esp.quando tudo que você quer é qualquer limite superior da estimativa, e você não se importa se ele está muito pessimista - o que eu acho que é provavelmente o que sua pergunta é sobre.

Se você realmente deseja responder sua pergunta para qualquer algoritmo o melhor que você pode fazer é aplicar a teoria.Além de simplista de "pior caso" de análise de eu ter encontrado Amortizado análise muito útil na prática.

Para o 1º caso, o loop interno é executado n-i vezes, de modo que o número total de execuções é a soma de i indo de 0 para n-1 (porque o inferior, não inferior ou igual) do n-i.Você começa, finalmente, n*(n + 1) / 2, então O(n²/2) = O(n²).

Para o 2º ciclo, i é entre 0 e n incluído para o loop externo;em seguida, o loop interno é executado quando j é estritamente maior do que n, qual é, então, impossível.

Além de usar o método mestre (ou uma de suas especializações), eu testar meu algoritmos experimentalmente.Isso não pode provar que qualquer especial complexidade classe é obtida, mas pode fornecer a garantia de que a análise matemática é apropriado.Para ajudar com essa certeza, eu uso ferramentas de cobertura de código em conjunto com minhas experiências, para garantir que eu sou o exercício de todos os casos.

Como um exemplo muito simples dizer que você queria fazer uma verificação de sanidade na velocidade da .NET framework da lista de classificação.Você poderia escrever algo como o seguinte e, em seguida, analisar os resultados no Excel para certificar-se de que não excede um n*log(n) da curva.

Neste exemplo eu medir o número de comparações, mas também é prudente examinar o tempo real necessário para cada tamanho de amostra.No entanto, em seguida, você terá que ser ainda mais cuidadoso com o que você está apenas medindo o algoritmo e não incluindo artefatos de sua infra-estrutura 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 também permitir um espaço de complexidades que também pode ser uma causa de preocupação se tem limitado a recursos de memória.Assim, por exemplo, você pode ouvir alguém querendo uma constante algoritmo de espaço, que é basicamente uma forma de dizer que a quantidade de espaço ocupado pelo algoritmo não depende de nenhuma fatores dentro do código.

Por vezes, a complexidade pode vir de como, muitas vezes, é algo chamado, como muitas vezes é um loop executado, como muitas vezes é a memória alocada, e assim por diante é outra parte para responder a esta pergunta.

Por último, O grande pode ser usado para o pior caso, melhor caso e amortização casos em que, geralmente, é o pior caso que é usada para descrever o quão ruim um algoritmo pode ser.

O que muitas vezes fica esquecido é o o esperado comportamento de seus algoritmos. Ele não altera o Grande-O de seu algoritmo, mas ele não se relacionam com a declaração de "otimização prematura...."

O comportamento esperado de seu algoritmo é -- muito estúpidos -- o quão rápido você pode esperar que o seu algoritmo para trabalhar sobre os dados que você é mais provável para ver.

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

Realmente a unha para baixo, você precisa ser capaz de descrever a distribuição de probabilidade da sua "entrada do espaço" (se é que você precisa para ordenar uma lista, como muitas vezes é que a lista já vai ser classificados?como muitas vezes é totalmente revertido?como muitas vezes é classificado?) Não é sempre possível que você sabe o que, mas às vezes você faz.

excelente pergunta!

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

Se você estiver usando o Big O, você está falando sobre o pior caso (mais sobre o que isso significa posterior).Além disso, não há capital theta para o caso médio e um grande omega para o melhor caso.

Confira este site para um lindo definição formal de Grande Ó: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) significa que existem constantes positivas c e k, tais que 0 ≤ f(n) ≤ cg(n) para todo n ≥ k.Os valores de c e k deve ser corrigido para a função f e não deve depender de n.

Ok, então agora o que entendemos por "melhores" e "piores" complexidades?

Este é, provavelmente, o mais claramente ilustrada através de exemplos.Por exemplo, se estamos usando a pesquisa linear para encontrar um número em uma matriz ordenada, em seguida, o pior caso é quando decidimos pesquisa para o último elemento da matriz como isto, como muitos passos, pois há itens na matriz.O melhor caso seria quando precisamos procurar a primeiro elemento desde que deverá ser feito após a primeira verificação.

O ponto de todos estes adjetivo-caso complexidades é que nós estamos procurando uma forma de gráfico a quantidade de tempo que um hipotético programa é executado para conclusão em termos de tamanho específico de variáveis.No entanto, para muitos algoritmos você pode argumentar que não há um único momento para um determinado tamanho de entrada.Observe que isso contradiz com o requisito fundamental de uma função, qualquer entrada deve ter mais de uma saída.Para vir até nós com vários funções para descrever um algoritmo de complexidade.Agora, mesmo que procurar uma matriz de tamanho n pode assumir diferentes quantidades de tempo, dependendo o que você está procurando na matriz e em função proporcionalmente ao n, podemos criar um informativo descrição do algoritmo a utilizar melhor dos casos, média de caso a caso, e o pior caso de classes.

Desculpe, isso é tão mal escrito e carece de muita informação técnica.Mas espero que de tempo de classes de complexidade mais fácil do que pensar.Uma vez que você se sentir confortável com essas torna-se uma simples questão de análise através do seu programa de e olhando para as coisas como o para-ciclos que dependem da matriz de tamanhos e raciocínio baseado em suas estruturas de dados que tipo de entrada de resultaria em casos simples e de entrada, o resultado seria pior dos casos.

Eu não sei como consegue resolver isso, mas a primeira coisa que as pessoas fazem é que nós exemplo o algoritmo de determinados padrões no número de operações realizadas, dizer 4n^2 + 2n + 1, temos 2 regras:

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

Se podemos simplificar f(x), onde f(x) é a fórmula para o número de operações realizadas, (4n^2 + 2n + 1 explicado acima), obtém-se o grande-O valor [O(n^2) neste caso].Mas isso teria para a conta para a interpolação de Lagrange, no programa, o que pode ser difícil de implementar.E que se o grande real-O valor foi O(2^n), e poderíamos ter algo como O(x^n), de modo que este algoritmo provavelmente não iria ser programável.Mas se alguém provar que eu estou errado, me dar o código ....

Para o código, o loop externo será executado para n+1 vezes, a '1' significa o processo que verifica a se eu ainda atende ao requisito.E loop interno é executado n vezes, n-2 vezes....Assim,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Para o código B, apesar de loop interno não iria intervir e executar o foo(), o inner loop será executado por n vezes depende de loop externo tempo de execução, que é O(n)

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

Big-S é apenas para comparar a complexidade dos programas, o que significa quão rápido eles estão crescendo quando as entradas estão aumentando e não exatamente o tempo que é gasto para realizar a ação.

IMHO no big-Ó fórmulas é melhor você não usar equações mais complexas (você pode apenas ficar no gráfico a seguir.) No entanto, você ainda pode usar outros mais precisos fórmula (3^n, n^3,...), mas mais do que isso pode ser, por vezes, enganosa!Então é melhor mantê-lo o mais simples possível.

Eu gostaria de enfatizar mais uma vez que aqui não queremos obter uma fórmula exata para o nosso algoritmo.Queremos apenas mostrar como ela cresce quando as entradas estão a crescer e a se comparar com os outros algoritmos em que sentido.Caso contrário, você seria melhor usar diferentes métodos de bench-marking.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow