¿Cuál es un método general para calcular la complejidad temporal de un algoritmo?

Tomemos un ejemplo simple. Supongamos que tiene una lista con n elementos y desea ponerla en orden alfabético, utilizando el siguiente algoritmo:

1. Revise la lista y encuentre la entrada que viene primero en orden alfabético.
2. Cambie eso con la entrada que actualmente está en la parte superior de la lista.
3. Ahora ve a través de las entradas 2 – n y encuentra la siguiente entrada
4. Intercambia eso con la entrada que está en segundo lugar.
5. Enjabonar, enjuagar, repetir.

Queremos contar cuántos pasos da esto. Primero, seamos un poco más claros acerca de cómo estamos haciendo esto:

  para (int i = 0; i 
  Espero no haber cometido ningún error vergonzoso en el código, pero el concepto al menos debería ser claro.  Para un valor dado de i , el ciclo interno se ejecuta a través de n - i veces, por lo que en total se ejecuta el código más interno 
  [matemáticas] n + (n - 1) +… + 1 = \ frac {1} {2} n ^ 2 + \ frac {1} {2} n [/ matemáticas] 
  veces.  Por supuesto, hay otro código que se está ejecutando aquí, y podríamos contarlo también, por ejemplo, cada una de las tres líneas de código que lleva a cabo el intercambio se ejecuta una vez cada vez que se ejecuta el bucle externo, por lo que contribuye 3n operaciones adicionales ;  luego está la única vez que me pongo a cero, todas las comparaciones e incrementos dentro del ciclo, etc. Sin embargo, una vez que sumamos todo esto, obtendremos una expresión cuadrática , es decir, algo de la forma [matemáticas] an ^ 2 + bn + c [/ matemáticas].  Para valores grandes de n, o en otras palabras, para listas lo suficientemente largas como para importar cuán eficiente es el algoritmo, dominará el término [math] n ^ 2 [/ math].  Por lo tanto, decimos que este algoritmo es [math] O (n ^ 2) [/ math]. 

    

En la práctica, las únicas complejidades computacionales de las que debe preocuparse son [matemáticas] O (1) [/ matemáticas], [matemáticas] O (n) [/ matemáticas], [matemáticas] O (\ log n) [/ matemáticas] , [matemática] O (n \ log n) [/ matemática], [matemática] O (n ^ 2) [/ matemática], [matemática] O (\ text {Tengo un pequeño conjunto de datos}) [/ matemática] & [matemáticas] O (\ text {demasiado maldito lento}) [/ matemáticas]

La evaluación comparativa simple generalmente puede decirle la diferencia entre estos casos.