algorithm - recursivos - Cómo encontrar la complejidad temporal de un algoritmo.

complejidad de algoritmos recursivos

Question

La pregunta

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

¿Qué he hecho antes de publicar una pregunta en SO?

He pasado por this , this y muchos otros enlaces.

Pero no donde pude encontrar una explicación clara y directa sobre cómo calcular la complejidad del tiempo.

Que sé yo ?

Diga por 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

Di por un bucle como el de abajo:

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

int i = 0; Esto será ejecutado una sola vez . El tiempo se calcula realmente para i=0 y no para la declaración.

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

i ++; Esto será ejecutado N veces.

Así que el número de operaciones requeridas por este bucle son

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

Nota: Esto todavía puede estar mal, ya que no confío en mi comprensión sobre el cálculo de la complejidad del tiempo

Qué quiero saber ?

Ok, entonces estos pequeños cálculos básicos creo que lo sé, pero en la mayoría de los casos he visto la complejidad del tiempo como

O (N), O (n2), O (log n), O (n!) .... y muchos other ,

¿Puede alguien ayudarme a entender cómo se calcula la complejidad de tiempo de un algoritmo? Estoy seguro de que hay muchos novatos como yo que quieren saber esto.

Answer 1

Cómo encontrar la complejidad temporal de un algoritmo.

Suma la cantidad de instrucciones de la máquina que 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 las instrucciones de la máquina 2N + 2 para describir esto como solo O(N) .

¿Por qué quitamos los dos 2 s?

Nos interesa 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 a medida que N aumenta? Supongamos que N es un millón.

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

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

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

Tradicionalmente, solo 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. La unidad de 2N no está bien definida en primer lugar de todos modos. Así que podemos multiplicar o dividir por un factor constante para llegar a la expresión más simple.

Entonces 2N convierte en solo N

Answer 2

Complejidad del tiempo con ejemplos.

1 - Operaciones básicas (aritmética, comparaciones, acceso a elementos de la matriz, asignación): el tiempo de ejecución es siempre constante O (1)

Ejemplo:

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

2 - Si es otra instrucción: toma solo el tiempo de ejecución máximo de dos o más declaraciones posibles.

Ejemplo:

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;

Entonces, la complejidad del pseudo código anterior es T (n) = 2 + 1 + max (1, 1 + 2) = 6. Por lo tanto, su gran oh es todavía constante T (n) = O (1).

3 - Bucle (para, mientras, repita): El tiempo de ejecución de esta declaración es el número de bucles multiplicado por el número de operaciones dentro de ese bucle.

Ejemplo:

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

Entonces, su complejidad es T (n) = 1 + 4n + 1 = 4n + 2. Por lo tanto, T (n) = O (n).

4 - Bucle anidado (bucle dentro del bucle): dado que hay al menos un bucle dentro del bucle principal, el tiempo de ejecución de esta declaración utilizó O (n ^ 2) u O (n ^ 3).

Ejemplo:

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;

Tiempo de ejecución común

Hay algunos tiempos de ejecución comunes al analizar un algoritmo:

1. O (1) - Tiempo constante Tiempo constante significa que el tiempo de ejecución es constante, no se ve afectado por el tamaño de entrada .

2. O (n) - Tiempo lineal Cuando un algoritmo acepta un tamaño de entrada, también realizará n operaciones.

3. O (log n): el algoritmo de tiempo logarítmico que tiene el tiempo de ejecución O (log n) es ligeramente más rápido que O (n). Comúnmente, el algoritmo divide el problema en problemas secundarios con el mismo tamaño. Ejemplo: algoritmo de búsqueda binaria, algoritmo de conversión binaria.

4. O (n log n) - Linearithmic Time Este tiempo de ejecución se encuentra a menudo en los "algoritmos de dividir y conquistar" que dividen el problema en sub problemas de forma recursiva y luego los combinan en n tiempo. Ejemplo: Combinar algoritmo de clasificación.

5. O (n ² ) - ¡Algoritmo de ordenación de burbuja de tiempo cuadrático!

6. O (n ³ ) - Tiempo cúbico Tiene el mismo principio con O (n ² ).

7. O (2 ⁿ ) - Tiempo exponencial Es muy lento a medida que aumenta la entrada, si n = 1000.000, T (n) sería 21000.000. El algoritmo de fuerza bruta tiene este tiempo de ejecución.

8. O (n!) - Factorial Time THE SLOWEST !!! Ejemplo: problema de vendedor de viajes (TSP)

Tomado de este artículo . Muy bien explicado debe dar una lectura.

Answer 3

Aunque hay algunas buenas respuestas para esta pregunta. Me gustaría dar otra respuesta aquí con varios ejemplos de loop .

• O (n) : la complejidad del tiempo de un bucle se considera como O (n) si las variables del bucle se incrementan / disminuyen en una cantidad constante. Por ejemplo, las siguientes funciones tienen una complejidad de tiempo 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) : la complejidad del tiempo de los bucles anidados es igual al número de veces que se ejecuta la instrucción más interna. Por ejemplo, los siguientes bucles de ejemplo tienen una complejidad de tiempo 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 ejemplo, la ordenación por selección y la ordenación por inserción tienen una complejidad de tiempo O (n ^ 2) .

• O (Logn) La complejidad del tiempo de un bucle se considera como O (Logn) si las variables del bucle se dividen / multiplican por una cantidad 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 ejemplo, Binary Search tiene una complejidad de tiempo O (Logn) .

• O (LogLogn) La complejidad del tiempo de un bucle se considera como O (LogLogn) si las variables del bucle se reducen / aumentan exponencialmente en una cantidad 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
  }

Un ejemplo de análisis de complejidad de tiempo.

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

Análisis :

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.

Entonces, la complejidad del tiempo total del algoritmo anterior es (n + n/2 + n/3 + … + n/n) , que se convierte en n * (1/1 + 1/2 + 1/3 + … + 1/n)

Lo importante de la serie (1/1 + 1/2 + 1/3 + … + 1/n) es igual a O (Logn) . Entonces, la complejidad del tiempo del código anterior es O (nLogn) .

Ref: 1 2 3

Answer 4

Cuando analiza el código, debe analizarlo línea por línea, contando cada operación / reconociendo la complejidad del tiempo; al final, debe sumarlo para obtener una imagen completa.

Por ejemplo, puede tener un bucle simple con complejidad lineal , pero más adelante en ese mismo programa puede tener un bucle triple que tiene complejidad cúbica , por lo que su programa tendrá complejidad cúbica . La función de orden de crecimiento entra en juego aquí.

Veamos cuáles son las posibilidades de complejidad de tiempo de un algoritmo, puede ver el orden de crecimiento que mencioné anteriormente:

• El tiempo constante tiene un orden de crecimiento 1 , por ejemplo: a = b + c .

• El tiempo logarítmico tiene un orden de crecimiento LogN , generalmente ocurre cuando se divide algo a la mitad (búsqueda binaria, árboles, incluso bucles) o se multiplica algo de la misma manera.

• Lineal , orden de crecimiento es N , por ejemplo.

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

• Linearithmic , el orden de crecimiento es n*logN , generalmente ocurre en los algoritmos de dividir y conquistar.

• Cúbico , orden de crecimiento N^3 , ejemplo clásico es un bucle triple en el que se comprueban todos los trillizos:

  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 , el orden de crecimiento 2^N , generalmente ocurre cuando realiza una búsqueda exhaustiva, por ejemplo, verifique los subconjuntos de algún conjunto.

Answer 5

En términos generales, la complejidad del tiempo es una forma de resumir cómo aumenta el número de operaciones o el tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de la entrada.

Como la mayoría de las cosas en la vida, un cóctel puede ayudarnos a entender.

EN)

Cuando llegas a la fiesta, tienes que darle la mano a todos (hacer una operación en cada artículo). A medida que aumenta el número de asistentes N , el tiempo / trabajo que le tomará dar la mano a todos aumenta a medida que O(N) .

¿Por qué O(N) y no cN ?

Existe una variación en la cantidad de tiempo que toma dar la mano a las personas. Podrías promediar esto y capturarlo en una constante c . Pero la operación fundamental aquí (estrechar la mano a todos) siempre sería proporcional a O(N) , sin importar lo que c fuera. Al debatir si deberíamos ir a un cóctel, a menudo nos interesa más el hecho de que tendremos que reunirnos con todos que en el detalle de cómo se ven esas reuniones.

O (N ^ 2)

El anfitrión de la fiesta de cóctel quiere que juegues un juego tonto en el que todos se encuentren con todos los demás. Por lo tanto, debe conocer N-1 otras personas de la N-1 y, debido a que la siguiente persona ya lo ha conocido, debe conocer a personas de la N-2 , y así sucesivamente. La suma de esta serie es x^2/2+x/2 . A medida que aumenta el número de asistentes, el término x^2 se agranda rápidamente , por lo que simplemente eliminamos todo lo demás.

O (N ^ 3)

Debe reunirse con todos los demás y, durante cada reunión, debe hablar sobre todos los demás en la sala.

O (1)

El anfitrión quiere anunciar algo. Ellos tocan una copa de vino y hablan en voz alta. Todos los escuchan. Resulta que no importa cuántos asistentes haya, esta operación siempre lleva la misma cantidad de tiempo.

O (log N)

El anfitrión ha colocado a todos en la mesa en orden alfabético. Donde esta Dan Usted cree que debe estar en algún lugar entre Adam y Mandy (¡ciertamente no entre Mandy y Zach!). Dado eso, ¿está él entre George y Mandy? No. Debe estar entre Adam y Fred, y entre Cindy y Fred. Y así sucesivamente ... podemos ubicar a Dan de manera eficiente mirando la mitad del juego y luego la mitad de ese juego. En última instancia, nos fijamos en O (log_2 N) individuos.

O (N log N)

Puede encontrar dónde sentarse en la mesa utilizando el algoritmo anterior. Si una gran cantidad de personas viniera a la mesa, una a la vez, y todas hicieran esto, eso tomaría tiempo O (N log N) . Esto resulta ser el tiempo que lleva ordenar una colección de artículos cuando deben compararse.

Mejor / Peor Caso

Llegas a la fiesta y necesitas encontrar a Íñigo, ¿cuánto tiempo tomará? Depende de cuando llegues. Si todos están dando vueltas, ha llegado al peor de los casos: tomará O(N) tiempo. Sin embargo, si todos están sentados en la mesa, solo tomará tiempo O(log N) . O tal vez puede aprovechar el poder de grito de copa del anfitrión y tomará solo O(1) tiempo.

Suponiendo que el host no esté disponible, podemos decir que el algoritmo de búsqueda de Íñigos tiene un límite inferior de O(log N) y un límite superior de O(N) , dependiendo del estado del participante cuando llegue.

Espacio y comunicación

Las mismas ideas se pueden aplicar para comprender cómo los algoritmos utilizan el espacio o la comunicación.

Knuth ha escrito un buen artículo sobre el anterior titulado "La complejidad de las canciones" .

Teorema 2: Existen arbitrariamente largas canciones de complejidad O (1).

PRUEBA: (debido a Casey y la banda de sol). Considere las canciones que Sk define por (15), pero con

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

para todos los k.

Answer 6

Este es un excelente artículo: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

La respuesta a continuación se copia desde arriba (en caso de que se rompa el excelente enlace)

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 se pueda estimar en relación con N a medida que N se acerca al infinito. En general se puede pensar 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 puede dividirse por 2. Esto se debe a que el algoritmo divide el área de trabajo a 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 consiste en 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ítmica. Existen otras medidas de Big O como cúbica, exponencial y raíz cuadrada, pero no son tan comunes. La notación O grande se describe como O () donde es la medida. El algoritmo de ordenación rápida se describiría como O (N * log (N)).

Tenga en cuenta que nada de esto ha tenido en cuenta las medidas de mejor, promedio y 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. ;)

Answer 7

O (n) es una notación O grande utilizada para escribir la complejidad de tiempo de un algoritmo. Cuando sumas el número de ejecuciones en un algoritmo obtendrás una expresión como resultado 2N + 2, en esta expresión N es el término dominante (el término tiene el mayor efecto en la expresión si su valor aumenta o disminuye). Ahora O (N) es la complejidad del tiempo, mientras que N es el término dominante. Ejemplo

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

aquí el número total de ejecuciones para el bucle interno es n + 1 y el número total de ejecuciones para el bucle externo es n (n + 1) / 2, por lo que el número total de ejecuciones para el algoritmo completo es n + 1 + n (n + 1/2 ) = (n ^ 2 + 3n) / 2. aquí n ^ 2 es el término dominante, por lo que la complejidad del tiempo para este algoritmo es O (n ^ 2)

Answer 8

Sé que esta pregunta se remonta a un tiempo atrás y hay algunas respuestas excelentes aquí, sin embargo, quería compartir un poco más para las personas con mentalidad matemática que se encontrarán en esta publicación. El teorema del Maestro es otra cosa útil que se debe saber al estudiar la complejidad. No lo vi mencionado en las otras respuestas.

Answer 9

Tomado de aquí - Introducción a la complejidad del tiempo de un algoritmo

1. Introducción

En informática, la complejidad del tiempo 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. Gran notación O

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

Por ejemplo, si el tiempo requerido por un algoritmo en todas las entradas de tamaño n es a lo sumo 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)
• n = O (n ² )
• log (n) = O (n)
• 2 n + 1 = O (n)

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:

• array: accediendo a cualquier elemento
• pila de tamaño fijo: métodos push y pop
• cola de tamaño fijo: métodos de puesta en cola y salida de cola

4. O (n) Tiempo lineal

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

Considere los siguientes ejemplos, a continuación estoy buscando linealmente un elemento, esto tiene una complejidad de tiempo 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:

• Array: Búsqueda lineal, Traversing, Buscar mínimo, etc.
• ArrayList: contiene el método
• Cola: contiene método

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

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: Binary Search

Recuerde el juego de las "veinte preguntas": la tarea es adivinar el valor de un número oculto en un intervalo. Cada vez que hace una conjetura, se le dice si su conjetura es demasiado alta o demasiado baja. El juego de veinte preguntas implica una estrategia que usa tu 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 (n2) 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.

Ejemplos:

• Ordenamiento de burbuja
• Selección de selección
• Tipo de inserción

7. Algunos enlaces útiles

• Big-O conceptos erróneos
• Determinar la complejidad del algoritmo
• bigocheatsheet.com