Cómo encontrar la complejidad de tiempo de un algoritmo

La pregunta

¿Cómo encontrar la complejidad del tiempo de un algoritmo?

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

He pasado por esto , este y muchos otros enlaces

Pero en ningún lugar pude encontrar una explicación clara y directa de cómo calcular la complejidad del tiempo.

Que sé yo ?

Di 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 ciclo como el siguiente:

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

int i = 0; Esto se ejecutará solo una vez . El tiempo en realidad se calcula para i=0 y no para la statement.

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

i ++; Esto se ejecutará N veces

Entonces, el número de operaciones requeridas por este ciclo son

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

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

Qué quiero saber ?

Bien, estos pequeños cálculos básicos creo que 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 otros ,

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

Cómo encontrar la complejidad de tiempo de un algoritmo

Suma la cantidad de instrucciones de 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 simplificador.

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

¿Por qué eliminamos los dos 2 s?

Estamos interesados ​​en el rendimiento del algoritmo a medida que N se vuelve grande.

Considera los dos términos 2N y 2.

¿Cuál es la influencia relativa de estos dos términos cuando N se vuelve grande? 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.

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 un 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. Entonces podemos multiplicar o dividir por un factor constante para llegar a la expresión más simple.

Entonces 2N convierte en solo N

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 el excelente enlace fracase)

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 cuando N se acerca al infinito. En general, puedes pensarlo así:

 statement; 

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

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

Es lineal. El tiempo de ejecución del ciclo 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 funcionamiento 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 entre 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 consiste en N bucles (iterativos o recursivos) que son logarítmicos, por lo tanto, 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. Hay otras medidas de Big O como cúbica, exponencial y raíz cuadrada, pero no son tan comunes. La notación de Big O se describe como O () donde está la medida. El algoritmo de quicksort se describiría como O (N * log (N)).

Tenga en cuenta que nada de esto ha tenido en cuenta las mejores, medias y peores medidas de 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 que he demostrado. También hay otras anotaciones, como el gran omega, el pequeño oy el gran Theta. Probablemente no los encontrará fuera del curso de análisis de algoritmos. 😉

Tomado de aquí – Introducción a la Complejidad del Tiempo 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. Gran notación O

La complejidad de tiempo de un algoritmo se expresa comúnmente utilizando 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 de manera asintótica, es decir, cuando el tamaño de la entrada va al infinito.

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

Algunos ejemplos más:

  • 1 = O (n)
  • n = O (n 2 )
  • 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 la entrada.

Ejemplos:

  • array: acceder a cualquier elemento
  • stack de tamaño fijo: métodos push y pop
  • cola de tamaño fijo: métodos de enqueue y dequeue

4. O (n) tiempo lineal

Se dice que un algoritmo se ejecuta en tiempo lineal si su ejecución en el tiempo 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, esto 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, Atravesar, Encontrar 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 ejecución de tiempo es proporcional al logaritmo del tamaño de entrada.

Ejemplo: búsqueda binaria

Recuerde el juego "veinte preguntas": la tarea consiste en adivinar el valor de un número oculto en un intervalo. Cada vez que adivina, se le informa si su conjetura es demasiado alta o demasiado baja. El juego de veinte preguntas implica una estrategia que usa su número de suposición 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 ejecución de tiempo es proporcional al cuadrado del tamaño de entrada.

Ejemplos:

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

7. Algunos enlaces útiles

  • Conceptos erróneos de Big-O
  • Determinando la Complejidad del Algoritmo
  • Big O Cheat Sheet

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

  • O (n) : Tiempo Complejidad de un bucle se considera como O (n) si las variables de bucle se incrementan / disminuyen en una cantidad constante. Por ejemplo, las siguientes funciones tienen O (n) complejidad de tiempo.

     // 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 de tiempo de los bucles nesteds es igual al número de veces que se ejecuta la instrucción más interna. Por ejemplo, los siguientes bucles de muestra tienen O (n ^ 2) complejidad de tiempo

     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, Selection sort y Insertion Sort tienen O (n ^ 2) complejidad de tiempo.

  • O (Logn) Tiempo Complejidad de un bucle se considera como O (Logn) si las variables de bucle se divide / multiplica 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, la búsqueda binaria tiene complejidad de tiempo O (inicio de sesión) .

  • O (LogLogn) Tiempo Complejidad de un bucle se considera como O (LogLogn) si las variables de 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 de tiempo del código anterior es O (nLogn) .


Ref: 1 2 3

Complejidad del tiempo con ejemplos

1 – Operaciones básicas (aritmética, comparaciones, acceso a los elementos de la matriz, asignación): el tiempo de ejecución siempre es 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 una statement else: solo tomando el tiempo máximo de ejecución 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 - Looping (para, while, repeat): El tiempo de ejecución para esta statement 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 - Loop nested (looping inside looping): Como hay al menos un bucle dentro del bucle principal, el tiempo de ejecución de esta instrucció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 común de ejecución

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

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

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

  3. O (log n) - Algoritmo de tiempo logarítmico que tiene un 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) - Tiempo Linearítmico Este tiempo de ejecución se encuentra a menudo en "algoritmos de dividir y conquistar" que dividen el problema en problemas secundarios recursivamente y luego los fusionan en n tiempo. Ejemplo: algoritmo Merge Sort.

  5. O (n 2 ) - ¡Algoritmo cuadrático Time Look Bubble Sort!

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

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

  8. ¡O (n!) - Tiempo factorial EL MÁS LENTO! Ejemplo: Problema del vendedor de viajes (TSP)

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

En términos generales, la complejidad del tiempo es una forma de resumir cómo crece 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 llegue a la fiesta, debe estrechar la mano de todos (realice una operación en cada elemento). A medida que aumente el número de asistentes N , el tiempo / trabajo que le tomará agitar la mano de todos aumenta como O(N) .

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

Existe una variación en la cantidad de tiempo que se necesita para estrechar la mano de las personas. Puede promediar esto y capturarlo en una constante c . Pero la operación fundamental aquí — estrechar la mano de todos — siempre sería proporcional a O(N) , sin importar qué c . 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 los detalles de las reuniones.

O (N ^ 2)

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

O (N ^ 3)

Debes conocer a todos los demás y, durante cada reunión, debes hablar sobre todos los demás en la sala.

O (1)

El anfitrión quiere anunciar algo. Tienden una copa de vino y hablan en voz alta. Todos los oyen. 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 puesto a todos en la mesa en orden alfabético. ¿Dónde está Dan? Razonas 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. Él 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 conjunto y luego la mitad de ese conjunto. En última instancia, observamos 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 vinieran a la mesa, una a la vez, y todas hicieran esto, eso tomaría el tiempo O (N log N) . Este resulta ser el tiempo que toma ordenar cualquier colección de artículos cuando deben compararse.

Mejor / Peor caso

Llegas a la fiesta y necesitas encontrar a Iñigo, ¿cuánto tiempo tomará? Depende de cuándo llegue. Si todo el mundo está dando vueltas, ha llegado al peor de los casos: le llevará tiempo a O(N) . Sin embargo, si todos están sentados en la mesa, solo tomarán O(log N) tiempo. O tal vez pueda aprovechar el poder de gritar copa de vino del anfitrión y solo le tomará O(1) vez.

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

Espacio y comunicación

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

Knuth ha escrito un buen artículo sobre el primero titulado “La complejidad de las canciones” .

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

PRUEBA: (debido a Casey y Sunshine Band). Considere las canciones Sk definidas por (15), pero con

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

para todos k.

Cuando estás analizando código, tienes que analizarlo línea por línea, contando cada operación / reconociendo la complejidad del tiempo, al final, tienes que sumrlo para obtener una imagen completa.

Por ejemplo, puede tener un bucle simple con complejidad lineal , pero más adelante en ese mismo progtwig puede tener un bucle triple que tiene complejidad cúbica , por lo que su progtwig tendrá complejidad cúbica . El orden funcional 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 multiplicando 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; 
  • Linearítmico , el orden de crecimiento es n*logN , generalmente ocurre en los algoritmos de división y conquista.

  • Cúbico , orden de crecimiento N^3 , el ejemplo clásico es un ciclo triple donde se controlan 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 , orden de crecimiento 2^N , generalmente ocurre cuando haces una búsqueda exhaustiva, por ejemplo, ver subconjuntos de algún conjunto.

Sé que esta pregunta se remonta y hay algunas respuestas excelentes aquí, sin embargo, quería compartir otro poco para las personas de mentalidad matemática que tropezarán en este post. El teorema de la Maestría es otra cosa útil para saber cuando se estudia la complejidad. No lo he visto mencionado en las otras respuestas.

O (n) es una notación O grande utilizada para escribir la complejidad del tiempo de un algoritmo. Cuando sums el número de ejecuciones en un algoritmo obtendrás una expresión en el resultado como 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 comlexidad de 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 son 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 así que la complejidad de tiempo para este algoritmo es O (n ^ 2)

Para sentir un algoritmo, a menudo hago esto de forma experimental. Simplemente cambie la entrada N y vea cuánto tarda el cálculo. Esto necesita algo de reflexión, ya que big-O describe la complejidad del tiempo en el peor caso del algoritmo, y encontrar el peor de los casos puede ser complicado.

Para hacerlo teóricamente, su enfoque me parece correcto: recorrer el progtwig (siempre eligiendo el camino más complejo en el tiempo), agregar los tiempos indiviales y deshacerse de todas las constantes / factores. Los bucles nesteds, los saltos, etc. pueden hacer esto bastante complejo, pero no puedo pensar en una bala de plata para resolver esto de otra manera.

También puede estar intercalado en http://en.wikipedia.org/wiki/Big_O_notation , a pesar de que es bastante matemático.

También acabo de encontrar http://en.wikipedia.org/wiki/Analysis_of_algorithms