¿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 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, el tiempo se calcula para i=0 y no para la declaración.

yo < NORTE; 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).

OK, 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.

178

Bonificación para aquellos interesados: The Big O Cheat Sheet bigochatsheet.com

- msanford

9 junio 2013 a las 22:12

2

¿Por qué Console.Write('¡Hola mundo!'); ¿No es una instrucción de máquina?

- Chetan

10/07/2017 a las 11:02

1

Relacionado/tal vez duplicado: Big O, ¿cómo se calcula/aproxima?

- Bernhard Barker

24 dic 2017 a las 17:24

2

@Chetan Si quieres decir que deberías considerar Console.Write al calcular la complejidad, eso es cierto, pero siemprees algo irrelevante en este caso, ya que eso solo cambia un factor constante, que O grande ignora (ver las respuestas), por lo que el resultado final sigue siendo una complejidad de O(N).

- Bernhard Barker

24 dic 2017 a las 17:39

2

Relacionado: ¿Cuál es una explicación en inglés sencillo de "Big O" ¿notación? y ¿Existe un sistema detrás de la magia del análisis de algoritmos?

- Bernhard Barker

31 de octubre, 2018 a las 11:00

------------------------------------

Cómo encontrar la complejidad temporal de un algoritmo

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

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

¿Por qué eliminamos los dos 2?

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

Considere los dos términos 2N y 2.

¿Cuál es la influencia relativa de estosdos términos a medida que N se hace 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 grande.

Así que ahora hemos pasado de 2N + 2 a 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 2N se convierte en simplemente N.

Respondido al

14 de junio de 2012 a las 11:25

Andrés Tomazos

Andrés Tomazos

66,9k

43

43 insignias de oro

191

191 insignias de plata

328

328 de bronce insignias

11

68

Oye, gracias por dejarme saber "por qué O(2N+2) a O(N)" muy bien explicado, pero esto era solo una parte de la pregunta más importante, quería que alguien señalara algún enlace a un recurso oculto o, en general, quería saber cómo terminar con el tiempo cComplejidades como O(N), O(n2), O(log n), O(n!), etc. Sé que puedo estar pidiendo mucho, pero aún así puedo intentarlo :{)

- Yasser Shaikh

14 de junio de 2012 a las 11:33

4

Bueno, la complejidad entre paréntesis es cuánto tiempo lleva el algoritmo, simplificado usando el método que he explicado. Calculamos cuánto tiempo tarda el algoritmo simplemente sumando el número de instrucciones de máquina que ejecutará. Podemos simplificar mirando sólo los bucles más ocupados y dividiéndolos por factores constantes como he explicado.

Yrew tomazos

14 de junio de 2012 a las 11:36

5

Dar un ejemplo en la respuesta habría sido de gran ayuda para futuros lectores. Simplemente entregar un enlace para el cual tengo que registrarme realmente no me ayuda cuando solo quiero leer un texto bien explicado.

- bad_keypoints

2 de enero de 2016 a las 4:48

4

Sugeriría ver al Dr. Naveen Garg (IIT Delhi Prof.) videos si desea obtener un buen conocimiento sobre DS y la complejidad del tiempo. Consulte el enlace.nptel.ac.in/courses/106102064

- Rohit Bandil

1 de octubre de 2016 a las 16:45

3

(cont.) Esta jerarquía tendría una altura del orden de log N. En cuanto a O(N!), mis analogías probablemente no sean suficientes, pero las permutaciones están en ese orden: es prohibitivamente empinado, más que cualquier polinomio o exponencial. ¡Hay exactamente 10! segundos en seis semanas pero el universo es menosun 20! segundos de antigüedad.

- John P.

25/02/2018 a las 2:59

------------------------------------

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 O grande. 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 verlo así:

statement;

Es constante. El tiempo de ejecución de la declaración no cambiará en relaciónhacia 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 centavosnsions 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> ) donde <type> es 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 mejores medidas, 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. ;)

Respondido

18 de enero de 2013 a las 10:04

Achow

Achow

8,618

6

6 insignias de oro

39

39 insignias de plata

49

49 insignias de bronce

7

15

El algoritmo de clasificación rápida, en el peor de los casos, tiene un tiempo de ejecución de N^2, aunque este comportamiento es raro.

-nbro

4 de marzo de 2015 a las 8:23

4

IIRC, o pequeña y omega grande se utilizan para la complejidad del mejor y promedio de los casos (siendo la O grande el peor de los casos), por lo que "medidas del mejor, promedio y peor de los casos". Cada uno tendría su propia notación O grande”. sería incorrecto. Hay incluso más símbolos con significados más específicos y CS no siempre utiliza el símbolo más apropiado. Por cierto, aprendí todos estos con el nombre de símbolos Landau. +1 de todos modos porque es la mejor respuesta.

– hiergiltdiestfu

8 de mayo de 2015 a las 7:43

1

@hiergiltdiestfu Big-O, Big-Omega, etc. se pueden aplicar a cualquiera de los tiempos de ejecución mejores, promedio o peor de un algoritmo. ¿Cómo se relacionan O y Ω con el peor y el mejor caso?

- Bernhard Barker

17 dic 2017 a las 9:34

1

Además, si alguien está buscando fo cómo calcular O grande para cualquier método: stackoverflow.com/a/60354355/4260691

OhadM

22/02/2020 a las 17:13

1

Una de las mejores explicaciones.

- Shivaraj Patil

21 de mayo de 2020 a las 6:04

------------------------------------

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 tTiempo 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 llega al infinito.

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

Algunos ejemplos más:

1 = O(n) norte = O(n2) 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: accesosing 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. 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: búsqueda binaria

Recuerde las "veinte preguntas" juego - la tarea esadivinar 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 (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 Orden de selección Tipo de inserción 7. Algunos enlaces útiles Conceptos erróneos de Big-O Determinar la complejidad del algoritmo Hoja de trucos de Big O Respondido al

27 de marzo de 2014 a las 13:14

Yasser Shaikh

Yasser Shaikh

47,3k

48

48 insignias de oro

204

204 insignias de plata

282

282 bronce insignias

0

------------------------------------

Varios ejemplos de bucle.

La complejidad temporal O(n) de un bucle se considera O(n) si las variables del bucle se incrementan o disminuyen en una cantidad constante. Por ejemplo, las siguientes funciones tienen complejidad temporal 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
  }

La complejidad temporal O(nc) de los bucles anidados es igual al número de veces que se ejecuta la declaración más interna. Por ejemplo, el siguienteLos bucles de muestra de ala tienen una complejidad de tiempo O(n2)

  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 temporal O(n2).

La complejidad temporal O(log n) de un bucle se considera O(log n) 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, la búsqueda binaria tiene una complejidad temporal O(log n).

La complejidad temporal O(log log n) de un bucle se considera O(log log n) si las variables del bucle se reducen o 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 temporal

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 temporal 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 las series (1/1 + 1/2 + 1/3 +… + 1/n) es unaredondear a O(log n). Entonces, la complejidad temporal del código anterior es O(n·log n).

Referencias:

1 2 3

Respondido al

2 de noviembre de 2015 a las 9:31

zangw

zangw

45,3k

21

21 insignias de oro

185

185 insignias de plata

221

221 de bronce insignias

4

2

@Simon, podría¿Puedes descubrir qué parte es incorrecta?

- zangw

19/09/2019 a las 12:39

1

Gracias por preguntar. Leí mal el código. Eliminé mi comentario. ¡Lo siento!

Simón

19/09/2019 a las 18:32

1

en el análisis debería ser O(n ^ 2).

- Koustuv Ganguly

9 de noviembre de 2020 a las 14:17

@zangw ¡Excelente explicación! ¿Puedes cambiar que la serie (1/1 + 1/2 + 1/3 +… + 1/n) sea igual a O(log n) como serie (1/1 + 1&# 47;2 + 1/3 + … + 1/n) está alrededor de log n en lugar de O(log n) para hacerlo más preciso. Y c en pseudocódigo para O(n^c) puede inducir a error a las personas diciendo que las 2 cs son iguales.

- Wenbo

19 de mayo de 2022 a las 3:52

------------------------------------

Complejidad del tiempo con ejemplos.

1 - Operaciones básicas (aritmética, comparaciones, acceso a los elementos del array, 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 - Declaración If then else: solo toma 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 pseudocódigo anterior es T(n) = 2 + 1 + max(1, 1+2) = 6. Por lo tanto, su gran oh sigue siendo constante T(n) = O(1) .

3 - Bucle (for, while, repetir): 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 une bucle dentro del bucle principal, el tiempo de ejecución de esta declaración usó 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

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

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.

O(n) – Tiempo lineal

Cuando un algoritmo acepta n tamaños de entrada, también realizará n operaciones.

O(log n) – Tiempo logarítmico

El algoritmo 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 subproblemas del mismo tamaño. Ejemplo: algoritmo de búsqueda binaria, algoritmo de conversión binaria.

O(n log n) – Tiempo lineal

Este tiempo de ejecución se encuentra a menudo en "divide & conquistarer algoritmos" que divide el problema en subproblemas de forma recursiva y luego los fusiona en n tiempo. Ejemplo: algoritmo de ordenación por combinación.

O(n2) – Tiempo cuadrático

¡Mira el algoritmo de clasificación de burbujas!

O(n3) – Tiempo cúbico

Tiene el mismo principio con O(n2).

O(2n) – Tiempo exponencial

Es muy lento a medida que la entrada aumenta, si n = 1.000.000, T(n) sería 21.000.000. El algoritmo Brute Force tiene este tiempo de ejecución.

O(n!) – Tiempo factorial

¡¡¡El más lento!!! Ejemplo: problema del viajante de comercio (TSP)

Está tomado de este artículo. Está muy bien explicado y deberías darle una lectura.

Respondido

19 de abril de 2014 a las 9:36

Yasser Shaikh

Yasser Shaikh

47,3k

48

48 insignias de oro

204

204 insignias de plata

282

282 bronce insignias

7

En el segundo ejemplo, escribiste visitantes = visitantes + 1 es 1 + 1 = 2. ¿Podrías explicarme por qué hiciste eso?

- Sajib Acharya

31 de diciembre de 2015 a las 9:09

3

@Sajib Acharya Míralo de derecha a izquierda. Primer paso: calcular visitantes + 1 Segundo paso: asignar valor del primer paso a los visitantes Entonces, la expresión anterior está formada por dos declaraciones; primer paso + segundo paso => 1+1=2

-Bozidar Sikanjic

12 de enero de 2016 a las 9:46

@nbro Por qué es 1+1 en edad = read(x) // (1+1) = 2

- Humty

13/03/2017 a las 19:33

@BozidarSikanjic Por qué es 1+1 en edad = read(x) // (1+1) = 2

- Humty

13/03/2017 a las 19:34

1

@Humty Consulta el comienzo de esta respuesta: read(x) // O(1) a = 10; // O(1) Primero es la llamada a la función => O(1) ///// Segundod es asignación, como dijo nbro, pero 10 es constante, por lo que el segundo es => O(1)...

-Bozidar Sikanjic

13/03/2017 a las 22:46

------------------------------------

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

Por ejemplo, puedes tener un bucle simple con complejidad lineal, pero más adelante en ese mismo programa puedes tener un bucle triple que tenga complejidad cúbica, por lo que tu programa tendrá complejidad cúbica. Aquí entra en juego el orden de crecimiento de las funciones.

Veamos cuáles son las posibilidades de la complejidad del tiempo.tipo de algoritmo, puedes 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 log N. Generalmente ocurre cuando divides algo por la mitad (búsqueda binaria, árboles e incluso bucles) o multiplicas algo de la misma manera.

Lineal. El orden de crecimiento es N, por ejemplo

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

Linearítmica. El orden de crecimiento es n·log N. Suele ocurrir en algoritmos de divide y vencerás.

Cúbico. El orden de crecimiento es N3. Un ejemplo clásico es un bucle triple en el que se comprueban todos los tripletes:

 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 es 2N. Suele ocurrir cuando haces una búsqueda exhaustiva, por ejemplo, revisas subconjuntos de algún conjunto.

Respondido al

5 de junio de 2016 a las 9:43

Aleksandar Makragić

Aleksandar Makragić

1.967

18

18 insignias de plata

32

32 insignias de bronce

1

Si este fuera el caso, ¿cuál sería la complejidad? para (int i = 0; i < N; i++) para (int j = i+1; j < N; j++) para (int k = j+1; k < N; k++) x = x + 2

&norteguión; usuario3156040

24/01/2020 a las 0:35

------------------------------------

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

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

O(N)

Cuando llegues a la fiesta, debes estrechar la mano de todos (realizar una operación en cada elemento). A medida que aumenta el número de asistentes N, el tiempo/trabajo que le llevará estrechar 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 lleva estrechar la mano de las personas. Podrías promediar esto y capturarlo.en una constante c. Pero la operación fundamental aquí (dar la mano a todos) siempre sería proporcional a O(N), sin importar cuál fuera c. Cuando debatimos si deberíamos ir a un cóctel, a menudo nos interesa más el hecho de que tendremos que conocer a todos que los detalles minuciosos de cómo serán esas reuniones.

O(N^2)

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

O(N^3)

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

O(1)

El anfitrión quiere anunciar algo. 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 el mismo tiempo.

O(logN)

El anfitrión ha colocado 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. Debe estar entre Adam y Fred, y entre Cindy y Fred. Y así sucesivamente... podemos localizar eficientemente a Dan mirando la mitad del conjunto y luego la mitad de ese conjunto. En última instancia, nos fijamos en O(log_2 N) individuos.

O(N Iniciar sesión N)

Podrías encontrar dónde sentartepropio en la mesa usando el algoritmo anterior. Si un gran número de personas vinieran a la mesa, una a la vez, y todos hicieran esto, tomaría O(N log N) tiempo. Resulta ser el tiempo que lleva ordenar cualquier colección de elementos cuando deben compararse.

Mejor/peor caso

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

Suponiendo que el host no está disponible, podemos decir que el algoritmo de búsqueda de Inigo tiene un límite inferior de O(log N) y un límite superior de O(N), dependiendodepende del estado de la fiesta cuando llegues.

Espacio y espacio 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 bonito 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 and the 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 los k.

1

Lo has logrado, ahora cada vez que gEn un cóctel, inconscientemente intentaré encontrar la complejidad temporal de cualquier evento divertido. Gracias por un ejemplo tan divertido.

- Sabunkar Tejas Sahailesh

4 de abril de 2020 a las 1:54

------------------------------------

Para las personas con mentalidad matemática: el teorema maestro es otra cosa útil que se debe saber al estudiar la complejidad.

Respondido al

4 de noviembre de 2015 a las 9:20

Kasa de genciana

Kasa de genciana

776

6

6 insignias de plata

10

10 insignias de bronce

------------------------------------

O(n) es la notación O grande que se utiliza para escribir la complejidad temporal de un algoritmo. Cuando sumas el número de ejecuciones en un algoritmo, obtendrás una expresión como resultado como 2N+2. En esta expresión, N es el término dominante (el término que tiene mayor efecto en la expresión si su valor aumenta o disminuye). Ahora O(N) es la complejidad temporal 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 todoalgoritmo son n + 1 + n(n+1/2) = (n2 + 3n)/2. Aquí n^2 es el término dominante, por lo que la complejidad temporal de este algoritmo es O(n2).

Respondido al

11 de marzo de 2013 a las 20:18

ifra khan

ifra khan

21

1

1 insignia de bronce

1

Re For i = 1 an;: ¿Qué lenguaje de programación funciona con for y while termina prematuramente con punto y coma?¿Algún pseudocódigo?

-Peter Mortensen

17/04/2022 a las 18:36

------------------------------------

Otras respuestas se concentran en la notación O grande y ejemplos prácticos. Quiero responder a la pregunta enfatizando la visión teórica. La explicación siguiente carece necesariamente de detalles; una excelente fuente para aprender la teoría de la complejidad computacional es Introducción a la teoría de la computación de Michael Sipser.

Máquinas de Turing

El modelo más extendido para investigar cualquier cuestión sobre computación es una máquina de Turing. Una máquina de Turing tiene una dCinta tridimensional formada por símbolos que se utiliza como dispositivo de memoria. Tiene un cabezal de cinta que se utiliza para escribir y leer en la cinta. Tiene una tabla de transición que determina el comportamiento de la máquina, que es un componente de hardware fijo que se decide cuando se crea la máquina. Una máquina de Turing funciona en pasos de tiempo discretos haciendo lo siguiente:

Lee el símbolo debajo del cabezal de la cinta. Dependiendo del símbolo y su estado interno, que solo puede tomar un número finito de valores, lee tres valores s, σ y X de su tabla de transición, donde s es un estado interno, σ es un símbolo y X es Derecha o Izquierda.

Cambia su estado interno a s.

Cambia el símbolo que ha leído a σ.

Mueve el cabezal de cinta un paso según la dirección en X.

Mac TuringLas máquinas son poderosos modelos de computación. Pueden hacer todo lo que su computadora digital puede hacer. Fueron introducidos antes de la llegada de las computadoras digitales modernas por el padre de la informática teórica y matemático: Alan Turing.

Complejidad del tiempo

Es difícil definir la complejidad temporal de un solo problema como "¿Tienen las blancas una estrategia ganadora en el ajedrez?" porque hay una máquina que corre por un solo paso dando la respuesta correcta: O la máquina que dice directamente 'No' o directamente 'Sí'. Para que funcione, definimos la complejidad temporal de una familia de problemas L, cada uno de los cuales tiene un tamaño, generalmente la longitud de la descripción del problema. Luego tomamos una máquina de Turing M que resuelve correctamente todos los problemas de esa familia. Cuando a M se le da un problemam de esta familia de tamaño n, lo resuelve en un número finito de pasos. Llamemos a f(n) el tiempo más largo posible que le toma a M resolver problemas de tamaño n. Luego decimos que la complejidad temporal de L es O(f(n)), lo que significa que hay una máquina de Turing que resolverá una instancia de tamaño n como máximo en un tiempo C.f(n) donde C es una constante independiente. de n.

¿No depende de las máquinas? ¿Pueden las computadoras digitales hacerlo más rápido?

¡Sí! Algunos problemas se pueden resolver más rápido mediante otros modelos de computación; por ejemplo, dos máquinas de Turing de cinta resuelven algunos problemas más rápido que aquellas con una sola cinta. Es por eso que los teóricos prefieren usar clases de complejidad robustas como NL, P, NP, PSPACE, EXPTIME, etc. Por ejemplo, P es la clase de problemas de decisión cuya complejidad temporal es O(p(n)) donde p es unpolinomio. La clase P no cambia incluso si agregas diez mil cintas a tu máquina de Turing, o utilizas otro tipo de modelos teóricos como máquinas de acceso aleatorio.

Una diferencia en teoría y práctica

Generalmente se supone que la complejidad temporal de la suma de enteros es O(1). Esta suposición tiene sentido en la práctica porque las computadoras usan una cantidad fija de bits para almacenar números para muchas aplicaciones. No hay razón para suponer tal cosa en teoría, por lo que la complejidad temporal de la suma es O(k), donde k es el número de bits necesarios para expresar el número entero.

Encontrar la complejidad temporal de una clase de problemas

La forma sencilla de mostrar que la complejidad temporal de un problema es O(f(n)) es construir una máquina de Turing que lo resuelva en tiempo O(f(n)). Creando máquinas de Turing para comLos problemas complejos no son triviales; uno necesita cierta familiaridad con ellos. Rara vez se proporciona una tabla de transición para una máquina de Turing y se describe en un nivel alto. Es más fácil ver cuánto tiempo tardará una máquina en detenerse a medida que uno se familiariza con ellas.

Mostrar que un problema no es O(f(n)) de complejidad temporal es otra historia... Aunque hay algunos resultados como el teorema de la jerarquía temporal, hay muchos problemas abiertos aquí. Por ejemplo, si los problemas en NP están en P, es decir, si se pueden resolver en tiempo polinómico, es uno de los siete problemas del premio del milenio en matemáticas, cuyo solucionador recibirá 1 millón de dólares.