Como encontrar a complexidade do tempo de um algoritmo

A questão

Como encontrar complexidade de tempo de um algoritmo?

O que eu fiz antes de postar uma pergunta no SO?

Eu passei por isso , este e muitos outros links

Mas não onde eu era capaz de encontrar uma explicação clara e direta sobre como calcular a complexidade do tempo.

O que eu sei ?

Diga por um código tão simples como o abaixo:

char h = 'y'; // This will be executed 1 time int abc = 0; // This will be executed 1 time 

Diga por um loop como o abaixo:

 for (int i = 0; i < N; i++) { Console.Write('Hello World !'); } 

int i = 0; Isso será executado apenas uma vez . O tempo é realmente calculado para i=0 e não a declaração.

i <N; Isso será executado N + 1 vezes

i ++; Isso será executado N vezes

Portanto, o número de operações requeridas por este loop é

{1+ (N + 1) + N} = 2N + 2

Nota: Isso ainda pode estar errado, já que não estou confiante sobre o meu entendimento sobre como calcular a complexidade do tempo

O que eu quero saber ?

Ok, então esses pequenos cálculos básicos eu acho que sei, mas na maioria dos casos eu vi a complexidade do tempo como

O (N), O (n2), O (log n), O (n!) …. e muitos outros ,

Alguém pode me ajudar a entender como calcular a complexidade do tempo de um algoritmo? Tenho certeza de que há muitos novatos como eu querendo saber disso.

Como encontrar a complexidade do tempo de um algoritmo

Você sum quantas instruções de máquina ele executará como uma function do tamanho de sua input e depois simplifica a expressão para o maior (quando N é muito grande) e pode include qualquer fator de constante de simplificação.

Por exemplo, vamos ver como simplificamos as instruções de máquina 2N + 2 para descrever isso apenas como O(N) .

Por que nós removemos os dois 2 s?

Estamos interessados ​​no desempenho do algoritmo quando N se torna grande.

Considere os dois termos 2N e 2.

Qual é a influência relativa desses dois termos quando N se torna grande? Suponha que N seja um milhão.

Então o primeiro termo é 2 milhões e o segundo termo é apenas 2.

Por esta razão, deixamos cair todos os maiores termos para grandes N.

Então, agora passamos de 2N + 2 para 2N .

Tradicionalmente, estamos interessados ​​apenas no desempenho até fatores constantes .

Isso significa que realmente não nos importamos se existe algum múltiplo constante de diferença no desempenho quando N é grande. A unidade de 2N não está bem definida em primeiro lugar. Assim, podemos multiplicar ou dividir por um fator constante para chegar à expressão mais simples.

Então 2N se torna apenas N

Este é um excelente artigo: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

A resposta abaixo é copiada de cima (no caso de o excelente link falhar)

A métrica mais comum para calcular a complexidade do tempo é a notação Big O. Isso remove todos os fatores constantes para que o tempo de execução possa ser estimado em relação a N, enquanto N se aproxima do infinito. Em geral, você pode pensar assim:

 statement; 

É constante. O tempo de execução da instrução não será alterado em relação a N.

 for ( i = 0; i < N; i++ ) statement; 

É linear. O tempo de execução do loop é diretamente proporcional a N. Quando N duplica, o mesmo acontece com o tempo de execução.

 for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; } 

É quadrático. O tempo de execução dos dois loops é proporcional ao quadrado de N. Quando N duplica, o tempo de execução aumenta em N * N.

 while ( low <= high ) { mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break; } 

É logarítmico. O tempo de execução do algoritmo é proporcional ao número de vezes que N pode ser dividido por 2. Isso ocorre porque o algoritmo divide a área de trabalho pela metade a cada iteração.

 void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); } 

É N * log (N). O tempo de execução consiste em N loops (iterativo ou recursivo) que são logarítmicos, portanto, o algoritmo é uma combinação de linear e logarítmica.

Em geral, fazer algo com cada item em uma dimensão é linear, fazer algo com cada item em duas dimensões é quadrático e dividir a área de trabalho pela metade é logarítmico. Existem outras medidas do Big O, como a raiz cúbica, exponencial e quadrada, mas elas não são tão comuns. A notação Big O é descrita como O () onde está a medida. O algoritmo de quicksort seria descrito como O (N * log (N)).

Observe que nada disso levou em consideração as melhores, médias e piores medidas de caso. Cada um teria sua própria notação Big O. Note também que esta é uma explicação muito simplista. Big O é o mais comum, mas também é mais complexo que eu mostrei. Há também outras notações, como o ômega grande, o pequeno e o teta grande. Você provavelmente não os encontrará fora de um curso de análise de algoritmo. 😉

Tomado daqui – Introdução à Complexidade do Tempo de um Algoritmo

1. Introdução

Na ciência da computação, a complexidade de tempo de um algoritmo quantifica a quantidade de tempo que um algoritmo leva para funcionar como uma function do comprimento da string que representa a input.

2. Notação Big O

A complexidade de tempo de um algoritmo é comumente expressa usando notação O grande, que exclui coeficientes e termos de ordem mais baixa. Quando expresso dessa maneira, a complexidade de tempo é descrita como assintoticamente, ou seja, à medida que o tamanho da input vai para o infinito.

Por exemplo, se o tempo requerido por um algoritmo em todas as inputs de tamanho n é no máximo 5n 3 + 3n, a complexidade de tempo assintótico é O (n3). Mais sobre isso depois.

Mais alguns exemplos:

  • 1 = O (n)
  • n = O (n 2 )
  • log (n) = O (n)
  • 2 n + 1 = O (n)

3. O (1) tempo constante:

Diz-se que um algoritmo é executado em tempo constante, se requerer a mesma quantidade de tempo, independentemente do tamanho da input.

Exemplos:

  • array: acessando qualquer elemento
  • pilha de tamanho fixo: methods push e pop
  • fila de tamanho fixo: methods de enfileiramento e de enfileiramento

4. O (n) Tempo Linear

Diz-se que um algoritmo é executado em tempo linear se sua execução temporal é diretamente proporcional ao tamanho da input, ou seja, o tempo cresce linearmente à medida que o tamanho da input aumenta.

Considere os seguintes exemplos, abaixo Estou linearmente procurando por um elemento, isto tem uma complexidade de tempo de O (n).

 int find = 66; var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 }; for (int i = 0; i < numbers.Length - 1; i++) { if(find == numbers[i]) { return; } } 

Mais exemplos:

  • Array: Linear Search, Traversing, Find mínimo etc
  • ArrayList: contém o método
  • Fila: contém o método

5. O (log n) tempo logarítmico:

Diz-se que um algoritmo é executado em tempo logarítmico se sua execução temporal for proporcional ao logaritmo do tamanho da input.

Exemplo: pesquisa binária

Lembre-se do jogo "vinte perguntas" - a tarefa é adivinhar o valor de um número oculto em um intervalo. Cada vez que você adivinha, você é informado se seu palpite é muito alto ou muito baixo. O jogo de vinte perguntas implica uma estratégia que usa seu número de palpite para reduzir pela metade o tamanho do intervalo. Este é um exemplo do método geral de solução de problemas conhecido como pesquisa binária

6. O (n2) Tempo Quadrático

Diz-se que um algoritmo é executado em tempo quadrático se sua execução temporal é proporcional ao quadrado do tamanho da input.

Exemplos:

  • Tipo de bolha
  • Seleção de seleção
  • Tipo de Inserção

7. Alguns links úteis

  • Big-O Misconceptions
  • Determinando a Complexidade do Algoritmo
  • Big O Cheat Sheet

Embora haja algumas boas respostas para esta questão. Eu gostaria de dar outra resposta aqui com vários exemplos de loop .

  • O (n) : Tempo A complexidade de um loop é considerada como O (n) se as variables ​​do loop forem incrementadas / decrementadas por um valor constante. Por exemplo, as seguintes funções têm complexidade de tempo O (n) .

     // Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions } 
  • O (n ^ c) : A complexidade de tempo dos loops nesteds é igual ao número de vezes que a instrução mais interna é executada. Por exemplo, os loops de amostra a seguir têm complexidade de tempo O (n ^ 2)

     for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions } 

    Por exemplo, a sorting de seleção e a sorting de inserção têm complexidade de tempo O (n ^ 2) .

  • O (Logn) Time A complexidade de um loop é considerada como O (Logn) se as variables ​​do loop forem divididas / multiplicadas por um valor constante.

     for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions } 

    Por exemplo, a pesquisa binária tem complexidade de tempo O (Logn) .

  • O (LogLogn) Tempo A complexidade de um loop é considerada como O (LogLogn) se as variables ​​de loop forem reduzidas / aumentadas exponencialmente por um valor constante.

     // Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions } 

Um exemplo de análise de complexidade de tempo

 int fun(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j < n; j += i) { // Some O(1) task } } } 

Análise :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

Assim, a complexidade temporal total do algoritmo acima é (n + n/2 + n/3 + … + n/n) , que se torna n * (1/1 + 1/2 + 1/3 + … + 1/n)

O importante da série (1/1 + 1/2 + 1/3 + … + 1/n) é igual a O (Logn) . Portanto, a complexidade temporal do código acima é O (nLogn) .


Ref: 1 2 3

Complexidade de tempo com exemplos

1 – Operações Básicas (aritmética, comparações, acessando elementos do array, atribuição): O tempo de execução é sempre constante O (1)

Exemplo:

 read(x) // O(1) a = 10; // O(1) a = 1.000.000.000.000.000.000 // O(1) 

2 – Se for o caso afirmação: Somente levando o tempo máximo de execução de duas ou mais declarações possíveis.

Exemplo:

 age = read(x) // (1+1) = 2 if age < 17 then begin // 1 status = "Not allowed!"; // 1 end else begin status = "Welcome! Please come in"; // 1 visitors = visitors + 1; // 1+1 = 2 end; 

Assim, a complexidade do pseudocódigo acima é T (n) = 2 + 1 + max (1, 1 + 2) = 6. Assim, seu grande oh ainda é constante T (n) = O (1).

3 - Looping (for, while, repeat): O tempo de execução desta declaração é o número de loops multiplicado pelo número de operações dentro desse loop.

Exemplo:

 total = 0; // 1 for i = 1 to n do begin // (1+1)*n = 2n total = total + i; // (1+1)*n = 2n end; writeln(total); // 1 

Assim, sua complexidade é T (n) = 1 + 4n + 1 = 4n + 2. Assim, T (n) = O (n).

4 - Loop Aninhado (looping dentro do loop): Como há pelo menos um loop dentro do loop principal, o tempo de execução desta instrução usou O (n ^ 2) ou O (n ^ 3).

Exemplo:

 for i = 1 to n do begin // (1+1)*n = 2n for j = 1 to n do begin // (1+1)n*n = 2n^2 x = x + 1; // (1+1)n*n = 2n^2 print(x); // (n*n) = n^2 end; end; 

Tempo de funcionamento comum

Existem alguns tempos de execução comuns ao analisar um algoritmo:

  1. O (1) - Tempo Constante Constante de Tempo significa que o tempo de execução é constante, não é afetado pelo tamanho da input .

  2. O (n) - Tempo Linear Quando um algoritmo aceita n tamanho de input, ele também executaria n operações.

  3. O (log n) - Algoritmo de tempo logarítmico que tem tempo de execução O (log n) é ligeiramente mais rápido que O (n). Geralmente, o algoritmo divide o problema em sub-problemas com o mesmo tamanho. Exemplo: algoritmo de busca binária, algoritmo de conversão binária.

  4. O (n log n) - Tempo Linearitmico Este tempo de execução é frequentemente encontrado em "dividir e conquistar algoritmos", que dividem o problema em sub-problemas de forma recursiva e, em seguida, mesclam-nos em n tempos. Exemplo: algoritmo Merge Sort.

  5. O (n 2 ) - Algoritmo de tempo quadrático

  6. O (n 3 ) - Tempo Cúbico Tem o mesmo princípio com O (n 2 ).

  7. O (2 n ) - Tempo Exponencial É muito lento à medida que a input aumenta, se n = 1000.000, T (n) seria 21.000.000. O algoritmo Brute Force tem esse tempo de execução.

  8. O (n!) - Tempo Fatorial O MAIS LENTO !!! Exemplo: Problema do Vendedor de Viagem (TSP)

Extraído deste artigo . Muito bem explicado deve dar uma lida.

Falando livremente, a complexidade de tempo é uma maneira de resumir como o número de operações ou tempo de execução de um algoritmo aumenta à medida que o tamanho da input aumenta.

Como a maioria das coisas na vida, um coquetel pode nos ajudar a entender.

EM)

Quando você chega na festa, você tem que apertar a mão de todos (faça uma operação em cada item). À medida que o número de participantes N aumenta, o tempo / trabalho que levará para apertar a mão de todos aumenta como O(N) .

Por que O(N) e não cN ?

Há uma variação na quantidade de tempo necessária para apertar a mão das pessoas. Você poderia calcular isso e capturá-lo em uma constante c . Mas a operação fundamental aqui – apertando as mãos de todos – seria sempre proporcional a O(N) , não importando o que fosse. Quando debatemos se deveríamos ir a um coquetel, geralmente ficamos mais interessados ​​no fato de que teremos que conhecer todo mundo do que nos mínimos detalhes de como são essas reuniões.

O (N ^ 2)

O anfitrião do coquetel quer que você jogue um jogo bobo, onde todo mundo conhece todo mundo. Portanto, você deve conhecer N-1 outras pessoas e, como a próxima pessoa já conheceu você, ela deve conhecer N-2 pessoas e assim por diante. A sum desta série é x^2/2+x/2 . À medida que o número de participantes aumenta, o termo x^2 fica muito rápido , então descartamos todo o resto.

O (N ^ 3)

Você tem que conhecer todos os outros e, durante cada reunião, você deve falar sobre todos os outros na sala.

O (1)

O host quer anunciar algo. Eles ding um copo de vinho e falam em voz alta. Todo mundo ouve eles. Acontece que não importa quantos participantes existem, essa operação sempre leva o mesmo tempo.

O (log N)

O anfitrião colocou todos na mesa em ordem alfabética. Onde está Dan? Você raciocina que ele deve estar em algum lugar entre Adam e Mandy (certamente não entre Mandy e Zach!). Dado isso, ele está entre George e Mandy? Não. Ele deve estar entre Adam e Fred e entre Cindy e Fred. E assim por diante … podemos localizar Dan com eficiência olhando para metade do set e depois para metade desse set. Em última análise, olhamos para os indivíduos O (log_2N) .

O (N log N)

Você pode encontrar onde sentar na mesa usando o algoritmo acima. Se um grande número de pessoas chegasse à mesa, uma de cada vez, e todas fizessem isso, isso levaria o tempo de O (N log N) . Isso é o tempo que leva para classificar qualquer coleção de itens quando eles devem ser comparados.

Melhor / pior caso

Você chega na festa e precisa encontrar o Inigo – quanto tempo vai demorar? Depende de quando você chega. Se todo mundo estiver andando por aí, você terá atingido o pior caso: levará O(N) tempo. No entanto, se todos estiverem sentados à mesa, o tempo O(log N) será reduzido. Ou talvez você possa alavancar o poder de gritar de wineglass do host e levará apenas O(1) tempo.

Supondo que o host não esteja disponível, podemos dizer que o algoritmo de localização do Inigo possui um limite inferior de O(log N) e um limite superior de O(N) , dependendo do estado da parte quando você chega.

Espaço e Comunicação

As mesmas ideias podem ser aplicadas para entender como os algoritmos usam espaço ou comunicação.

Knuth escreveu um bom artigo sobre o primeiro intitulado “The Complexity of Songs” .

Teorema 2: Existem músicas arbitrariamente longas de complexidade O (1).

PROVA: (devido a Casey e a banda de sol). Considere as músicas Sk definidas por (15), mas com

 V_k = 'That's the way,' U 'I like it, ' U U = 'uh huh,' 'uh huh' 

para todos k.

Quando você está analisando o código, você tem que analisá-lo linha por linha, contando cada operação / reconhecendo a complexidade do tempo, no final, você tem que resumir para obter uma imagem completa.

Por exemplo, você pode ter um loop simples com complexidade linear , mas mais tarde nesse mesmo programa você pode ter um loop triplo que tem complexidade cúbica , então seu programa terá complexidade cúbica . A ordem de crescimento das funções entra em jogo aqui mesmo.

Vejamos quais são as possibilidades de complexidade de tempo de um algoritmo, você pode ver a ordem de crescimento que mencionei acima:

  • O tempo constante tem uma ordem de crescimento 1 , por exemplo: a = b + c .

  • O tempo logarítmico tem uma ordem de crescimento LogN , geralmente ocorre quando você está dividindo algo pela metade (pesquisa binária, trees, loops pares) ou multiplicando algo da mesma maneira.

  • Linear , a ordem de crescimento é N , por exemplo

     int p = 0; for (int i = 1; i < N; i++) p = p + 2; 
  • Linearítica , a ordem de crescimento é n*logN , geralmente ocorre em algoritmos de divisão e conquista.

  • Cúbico , ordem de crescimento N^3 , exemplo clássico é um loop triplo onde você verifica todos os trigêmeos:

     int x = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) x = x + 2 
  • Exponencial , ordem de crescimento 2^N , geralmente ocorre quando você faz uma pesquisa exaustiva, por exemplo, verificar subconjuntos de algum conjunto.

Eu sei que esta pergunta vai um caminho de volta e há algumas excelentes respostas aqui, no entanto, eu queria compartilhar um pouco mais para as pessoas de mentalidade matemática que tropeçarão neste post. O teorema do mestre é outra coisa útil para se saber quando se estuda complexidade. Eu não vi isso mencionado nas outras respostas.

O (n) é uma notação O grande usada para escrever a complexidade do tempo de um algoritmo. Quando você sum o número de execuções em um algoritmo, você obtém uma expressão no resultado como 2N + 2, nessa expressão N é o termo dominante (o termo tendo maior efeito na expressão se seu valor aumentar ou diminuir). Agora O (N) é a comple- xidade do tempo enquanto N está dominando o termo. Exemplo

 For i= 1 to n; j= 0; while(j<=n); j=j+1; 

aqui o número total de execuções para o loop interno são n + 1 e o número total de execuções para o loop externo são n (n + 1) / 2, então o número total de execuções para o algoritmo inteiro é n + 1 + n (n + 1/2 ) = (n ^ 2 + 3n) / 2. aqui n ^ 2 é o termo dominante, então a complexidade de tempo para este algoritmo é O (n ^ 2)

Para ter uma ideia de um algoritmo, faço isso com frequência experimentalmente. Basta variar a input N e ver quanto tempo demora a computação. Isso precisa de algum pensamento, já que big-O descreve a complexidade do algoritmo no pior caso, e encontrar o pior caso pode ser complicado.

Para fazer isso teoricamente, sua abordagem parece certa para mim: percorrer o programa (sempre escolhendo o caminho mais complexo do tempo), adicionar os tempos individuais e se livrar de todas as constantes / fatores. Loops, saltos, etc. nesteds podem tornar isso bastante complexo, mas não consigo pensar em uma bala de prata para resolver isso de outra forma.

Você também pode se interessar por http://en.wikipedia.org/wiki/Big_O_notation , apesar de ser bastante matemático.

Eu também encontrei http://en.wikipedia.org/wiki/Analysis_of_algorithms