Como encontrar a complexidade temporal de um algoritmo

A questão

Como encontrar a complexidade temporal 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 um código tão simples como o código abaixo:

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

Diga 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=0e 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 exigidas por esse loop é

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

Nota: Isso ainda pode estar errado, pois não tenho certeza sobre meu entendimento sobre o cálculo da complexidade do tempo

O que eu quero saber ?

Ok, 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 de tempo de um algoritmo? Estou certo de que há muitos novatos como eu querendo saber disso.

Como encontrar a complexidade temporal de um algoritmo

Você adiciona quantas instruções de máquina serão executadas em função do tamanho de sua entrada e, em seguida, simplifica a expressão para o termo maior (quando N é muito grande) e pode incluir qualquer fator constante simplificador.

Por exemplo, vamos ver como simplificamos 2N + 2as instruções da máquina para descrevê-las como justas O(N).

Por que removemos os dois 2s?

Estamos interessados ​​no desempenho do algoritmo à medida que 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 esse motivo, eliminamos todos os termos, exceto os maiores, para N. grande

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

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

Isso significa que realmente não nos importamos se há 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 obter a expressão mais simples.

Então 2Nse torna justo 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 (caso o excelente link falhe)

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 à medida que 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 dobra, o tempo de execução também.

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 dobra, 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 ao meio 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 (iterativos ou recursivos) que são logarítmicos, portanto, o algoritmo é uma combinação de linear e logarítmico.

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 raiz cúbica, exponencial e quadrada, mas elas não são tão comuns. A notação Big O é descrita como O ( <type> )onde <type>está a medida. O algoritmo quicksort seria descrito como O ( N * log ( N ) ).

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

Retirado daqui - Introdução à complexidade temporal de um algoritmo

1. Introdução

Na ciência da computação, a complexidade do tempo de um algoritmo quantifica a quantidade de tempo gasto por um algoritmo para ser executado em função do comprimento da string que representa a entrada.

2. Notação Big O

A complexidade temporal de um algoritmo é comumente expressa usando a notação O grande, que exclui coeficientes e termos de ordem inferior. Quando expressa dessa maneira, a complexidade do tempo é descrita assintoticamente, ou seja, conforme o tamanho da entrada chega ao infinito.

Por exemplo, se o tempo exigido por um algoritmo em todas as entradas de tamanho n for no máximo 5n ³ + 3n, a complexidade do tempo assintótico será O (n ³ ). Mais sobre isso mais tarde.

Mais alguns exemplos:

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

3. O (1) Tempo constante:

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

Exemplos:

• array: acessando qualquer elemento
• pilha de tamanho fixo: métodos push e pop
• fila de tamanho fixo: métodos de enfileiramento e desenfileiramento

4. O (n) Tempo Linear

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

Considere os exemplos a seguir, abaixo, estou procurando linearmente um elemento, que 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:

• Matriz: Pesquisa Linear, Atravessar, Encontrar o mínimo, etc.
• ArrayList: contém o método
• Fila: contém o método

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

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

Exemplo: Pesquisa Binária

Lembre-se do jogo das "vinte perguntas" - a tarefa é adivinhar o valor de um número oculto em um intervalo. Cada vez que você adivinhar, será 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 (n ² ) Tempo quadrático

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

Exemplos:

• Tipo de bolha
• Classificação da seleção
• Classificação de inserção

7. Alguns links úteis

• Equívocos do Big-O
• Determinando a complexidade do algoritmo
• Big O - Folha de dicas

Embora haja algumas boas respostas para esta pergunta. Gostaria de dar outra resposta aqui com vários exemplos de loop.

• O (n) : A complexidade temporal de um loop é considerada como O (n) se as variáveis ​​do loop forem incrementadas / decrementadas por uma quantidade 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 temporal dos loops aninhados é igual ao número de vezes que a instrução mais interna é executada. Por exemplo, os seguintes exemplos de loops 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, Classificação de seleção e Classificação de inserção têm complexidade de tempo O (n ^ 2) .

• Tempo O (Logn) A complexidade de um loop é considerada O (Logn) se as variáveis ​​do loop forem divididas / multiplicadas por uma quantidade 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 possui complexidade de tempo O (Logn) .

• Tempo (O LogLogn) A complexidade de um loop é considerada O (LogLogn) se as variáveis ​​do loop forem reduzidas / aumentadas exponencialmente por uma quantidade 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.

Portanto, a complexidade total do tempo do algoritmo acima é (n + n/2 + n/3 + … + n/n), que se tornan * (1/1 + 1/2 + 1/3 + … + 1/n)

O importante das séries (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 temporal com exemplos

1 - Operações básicas (aritmética, comparações, acesso aos 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 - Instrução If else else: Somente o tempo máximo de execução de duas ou mais instruçõ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;

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

3 - Looping (para, enquanto repita): O tempo de execução para esta instrução é o número de ciclos multiplicado pelo número de operações dentro desse ciclo.

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

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

4 - Loop aninhado (loop dentro do loop): Como existe pelo menos um loop dentro do loop principal, o tempo de execução dessa 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 execução comum

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

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

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

3. O (log n) - O algoritmo de tempo logarítmico que possui tempo de execução O (log n) é um pouco mais rápido que O (n). Geralmente, o algoritmo divide o problema em subproblemas do mesmo tamanho. Exemplo: algoritmo de pesquisa binária, algoritmo de conversão binária.

4. O (n log n) - Tempo linear linear Esse tempo de execução é freqüentemente encontrado em "algoritmos de dividir e conquistar", que dividem o problema em subproblemas recursivamente e os mesclam em n tempo. Exemplo: algoritmo Merge Sort.

5. O (n ² ) - Algoritmo de classificação de bolhas com aparência de tempo quadrático!

6. O (n ³ ) - Tempo cúbico Tem o mesmo princípio que O (n ² ).

7. O (2 ⁿ ) - Tempo exponencial É muito lento à medida que a entrada aumenta, se n = 1000.000, T (n) for 21000.000. O algoritmo Brute Force tem esse tempo de execução.

8. O (n!) - Tempo fatorial O MAIS LENTO !!! Exemplo: Problema do vendedor de viagens (TSP)

Retirado deste artigo . Muito bem explicado deve dar uma leitura.

Ao analisar o código, você deve analisá-lo linha a linha, contando todas as operações / reconhecendo a complexidade do tempo; no final, você deve somar para obter uma imagem completa.

Por exemplo, você pode ter um loop simples com complexidade linear , mas, posteriormente, no mesmo programa, um loop triplo que possui complexidade cúbica ; portanto, seu programa terá complexidade cúbica . A ordem das funções de crescimento entra em ação aqui.

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

• Constante de tempo tem uma ordem de crescimento1, por exemplo:a = b + c.

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

• Linear , ordem de crescimento éN, por exemplo

  int p = 0;
  for (int i = 1; i < N; i++)
    p = p + 2;
  

• A ordem linear de crescimento én*logN, geralmente, nos algoritmos de dividir e conquistar.

• Por ordem de crescimento cúbica , oN^3exemplo 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
  

• A ordem de crescimento exponencial2^N geralmente ocorre quando você faz uma pesquisa exaustiva, por exemplo, verifica subconjuntos de algum conjunto.

Em termos gerais, a complexidade do tempo é uma maneira de resumir como o número de operações ou o tempo de execução de um algoritmo aumenta à medida que o tamanho da entrada aumenta.

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

EM)

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

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

Há variação na quantidade de tempo que leva para apertar a mão das pessoas. Você pode calcular a média e capturá-lo em uma constante c. Mas a operação fundamental aqui - apertar a mão de todos - sempre seria proporcional O(N), independentemente do que cfosse. Ao debater se devemos ir a um coquetel, geralmente estamos mais interessados ​​no fato de termos de conhecer todos do que nos mínimos detalhes de como são essas reuniões.

O (N ^ 2)

O anfitrião da festa quer que você jogue um jogo bobo, onde todo mundo conhece todo mundo. Portanto, você deve conhecer N-1outras pessoas e, porque a próxima pessoa já o conheceu, elas devem conhecer N-2pessoas e assim por diante. A soma desta série é x^2/2+x/2. À medida que o número de participantes aumenta, o x^2termo aumenta rapidamente , então deixamos de lado todo o resto.

O (N ^ 3)

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

O (1)

O anfitrião quer anunciar algo. Eles bebem um copo de vinho e falam alto. Todo mundo os ouve. Acontece que não importa quantos participantes existem, essa operação sempre leva a mesma quantidade de tempo.

O (log N)

O anfitrião colocou todos na mesa em ordem alfabética. Onde está o 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 metade do set e depois metade do set. Por fim, olhamos para O (log_2 N) indivíduos.

O (N log N)

Você pode encontrar onde se sentar à mesa usando o algoritmo acima. Se um grande número de pessoas chegasse à mesa, uma de cada vez, e todas fizessem isso, isso levaria tempo O (N log N) . Esse é o tempo necessário 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ê chegar. Se todo mundo está andando por aí, você atinge o pior dos casos: levará O(N)tempo. No entanto, se todos estiverem sentados à mesa, levará apenas um O(log N)tempo. Ou talvez você possa aproveitar o poder de gritar do anfitrião e levar apenas um O(1)tempo.

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

Espaço e Comunicação

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

Knuth escreveu um belo 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 Sunshine Band). 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.

Sei que essa pergunta é um caminho de volta e há algumas excelentes respostas aqui, no entanto, eu gostaria de compartilhar outra parte para as pessoas de mente matemática que tropeçarão neste post. O teorema do mestre é outra coisa útil a saber quando se estuda a complexidade. Não o vi mencionado nas outras respostas.

O (n) é uma notação O grande usada para escrever a complexidade do tempo de um algoritmo. Quando você soma o número de execuções em um algoritmo, obtém uma expressão no resultado como 2N + 2, nessa expressão N é o termo dominante (o termo que tem maior efeito na expressão se seu valor aumentar ou diminuir). Agora O (N) é a comlexidade temporal, enquanto N é o termo dominante. 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 é n + 1 e o número total de execuções para o loop externo é n (n + 1) / 2; portanto, 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, portanto a complexidade de tempo para esse algoritmo é O (n ^ 2)