¿Cómo puedo encontrar la complejidad temporal de un algoritmo?

Revisé la búsqueda en Google y Stack Overflow , pero en ninguna parte pude encontrar una explicación clara y directa sobre cómo calcular la complejidad del tiempo.

¿Qué sé ya?

Diga para un código tan simple como el siguiente:

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

Diga para un bucle como el siguiente:

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

int i=0;Esto se ejecutará sólo una vez .

En realidad, se calcula el tiempo i=0y no la declaración.

i < N;Esto se ejecutará N+1 veces .
i++Esto se ejecutará N veces .

Entonces, el número de operaciones requeridas por este bucle es {1+(N+1)+N} = 2N+2 . (Pero esto aún puede ser incorrecto, ya que no estoy seguro de haberlo entendido).

Bien, creo que conozco estos pequeños cálculos básicos, pero en la mayoría de los casos he visto la complejidad del tiempo como O(N), O(n^2), O(log n), O(n!) y muchos otros . .

Jun 14 '12 18:06 Yasser Shaikh

Cómo encontrar la complejidad temporal de un algoritmo

Suma cuántas instrucciones de máquina ejecutará en función del tamaño de su entrada y luego simplifica la expresión al término más grande (cuando N es muy grande) y puede incluir cualquier factor constante de simplificación.

Por ejemplo, veamos cómo simplificamos 2N + 2las instrucciones de la máquina para describir esto simplemente como O(N).

¿ Por qué eliminamos las dos 2s?

Estamos interesados en el rendimiento del algoritmo a medida que N aumenta.

Considere los dos términos 2N y 2.

¿Cuál es la influencia relativa de estos dos términos cuando N aumenta? Supongamos que N es un millón.

Entonces el primer término es 2 millones y el segundo término es solo 2.

Por esta razón, eliminamos todos los términos excepto los más grandes para N grande.

Entonces, ahora hemos pasado de 2N + 2a 2N.

Tradicionalmente, sólo nos interesa el rendimiento hasta factores constantes .

Esto significa que realmente no nos importa si hay algún múltiplo constante de diferencia en el rendimiento cuando N es grande. De todos modos, la unidad 2N no está bien definida. Entonces podemos multiplicar o dividir por un factor constante para llegar a la expresión más simple.

Entonces 2Nse vuelve justo N.

Jun 14 '2012 11:06 Andrew Tomazos

Este es un artículo excelente: Complejidad temporal del algoritmo.

La siguiente respuesta está copiada de arriba (en caso de que el excelente enlace falle)

La métrica más común para calcular la complejidad del tiempo es la notación Big O. Esto elimina todos los factores constantes para que el tiempo de ejecución pueda estimarse en relación con N cuando N se acerca al infinito. En general, puedes pensarlo así:

statement;

Es constante. El tiempo de ejecución de la declaración no cambiará en relación con N.

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

Es lineal. El tiempo de ejecución del bucle es directamente proporcional a N. Cuando N se duplica, también lo hace el tiempo de ejecución.

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

Es cuadrático. El tiempo de ejecución de los dos bucles es proporcional al cuadrado de N. Cuando N se duplica, el tiempo de ejecución aumenta en 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;
}

Es logarítmico. El tiempo de ejecución del algoritmo es proporcional al número de veces que N se puede dividir por 2. Esto se debe a que el algoritmo divide el área de trabajo por la mitad con cada iteración.

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

Es N * log (N). El tiempo de ejecución consta de N bucles (iterativos o recursivos) que son logarítmicos, por lo que el algoritmo es una combinación de lineal y logarítmico.

En general, hacer algo con cada elemento en una dimensión es lineal, hacer algo con cada elemento en dos dimensiones es cuadrático y dividir el área de trabajo por la mitad es logarítmico. Existen otras medidas de Big O, como la raíz cúbica, exponencial y cuadrada, pero no son tan comunes. La notación O grande se describe como O ( <type> )dónde <type>está la medida. El algoritmo de clasificación rápida se describiría como O (N * log(N )).

Tenga en cuenta que nada de esto ha tenido en cuenta las medidas del mejor, el promedio y el peor de los casos. Cada uno tendría su propia notación Big O. También tenga en cuenta que esta es una explicación MUY simplista. Big O es el más común, pero también es más complejo de lo que he mostrado. También hay otras notaciones como omega grande, o pequeña y theta grande. Probablemente no los encontrará fuera de un curso de análisis de algoritmos. ;)

Jan 18 '2013 10:01 Achow

Tomado de aquí: Introducción a la complejidad temporal de un algoritmo

1. Introducción

En informática, la complejidad temporal de un algoritmo cuantifica la cantidad de tiempo que tarda un algoritmo en ejecutarse en función de la longitud de la cadena que representa la entrada.

2. Notación O grande

La complejidad temporal de un algoritmo se expresa comúnmente mediante notación O grande, que excluye coeficientes y términos de orden inferior. Cuando se expresa de esta manera, se dice que la complejidad del tiempo se describe asintóticamente, es decir, cuando el tamaño de entrada tiende a infinito.

Por ejemplo, si el tiempo requerido por un algoritmo en todas las entradas de tamaño n es como máximo 5n ³ + 3n, la complejidad del tiempo asintótico es O(n ³ ). Más sobre eso más adelante.

Algunos ejemplos más:

1 = O(n)
norte = O(norte ² )
registro(norte) = O(norte)
2 norte + 1 = O (norte)

3. O (1) tiempo constante:

Se dice que un algoritmo se ejecuta en tiempo constante si requiere la misma cantidad de tiempo independientemente del tamaño de entrada.

Ejemplos:

matriz: acceder a cualquier elemento
pila de tamaño fijo: métodos push y pop
cola de tamaño fijo: métodos de poner en cola y quitar de la cola

4. O (n) tiempo lineal

Se dice que un algoritmo se ejecuta en tiempo lineal si el tiempo de ejecución es directamente proporcional al tamaño de la entrada, es decir, el tiempo crece linealmente a medida que aumenta el tamaño de la entrada.

Considere los siguientes ejemplos. A continuación estoy buscando linealmente un elemento, y este tiene una complejidad temporal 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;
    }
}

Más ejemplos:

Matriz: búsqueda lineal, recorrido, búsqueda mínima, etc.
ArrayList: contiene el método
Cola: contiene método

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

Se dice que un algoritmo se ejecuta en tiempo logarítmico si su tiempo de ejecución es proporcional al logaritmo del tamaño de entrada.

Ejemplo: búsqueda binaria

Recuerde el juego de las "veinte preguntas": la tarea consiste en adivinar el valor de un número oculto en un intervalo. Cada vez que usted hace una suposición, se le indica si su suposición es demasiado alta o demasiado baja. El juego de veinte preguntas implica una estrategia que utiliza su número de conjetura para reducir a la mitad el tamaño del intervalo. Este es un ejemplo del método general de resolución de problemas conocido como búsqueda binaria.

6. O(n ² ) tiempo cuadrático

Se dice que un algoritmo se ejecuta en tiempo cuadrático si su tiempo de ejecución es proporcional al cuadrado del tamaño de entrada.