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 poristo, isto e muitos outros links
Mas não onde eu era capaz de encontrar uma explicação clara e direta de 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 apenasuma vez. O tempo é realmente calculado parai=0
e não a declaração.
i <N; Isso será executadoN + 1 vezes
i ++; Isso será executadoN 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 em 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
O (N), O (n2), O (log n), O (n!).... e muitosde outros,
Alguém pode me ajudar a entender como calcular a complexidade do tempo de um algoritmo? Eu tenho certeza que há muitos novatos como eu querendo saber disso.