¿Es esto técnicamente un algoritmo O (1) para "Hola mundo"?

117

¿Se clasificaría esto como un algoritmo O (1) para "¡Hola, mundo!" ??

public class Hello1
{
   public static void Main()
   {
      DateTime TwentyYearsLater = new DateTime(2035,01,01);
      while ( DateTime.Now < TwentyYearsLater )
      { 
          System.Console.WriteLine("It's still not time to print the hello ...");
      }
      System.Console.WriteLine("Hello, World!");
   }
}

Estoy pensando en usar el

DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{ 
   // ... 
}

fragmento de código como un bucle ocupado para incluirlo como una broma cada vez que alguien solicita un algoritmo de cierta complejidad. ¿Sería esto correcto?

Desarrollo web insatisfactorio
fuente
15
Esto es O(N)complejidad, noO(1)
Fabjan
19
@SubparWebDev No, no sabe cuántas veces pasará por el ciclo, incluso si conoce la diferencia exacta de tiempo entre el momento en que inicia el programa y la fecha especificada. Es depende de lo rápido que el funcionamiento de la computadora es, ¿qué otra cosa se ejecuta en él, cómo los horarios de la tarea de CPU, etc.
Servy
131
@Fabjan No hay nada de lo Nque dependa el algoritmo, por lo que no se puede decir que sea un algoritmo O (N).
Servicio
29
Técnicamente no hay entrada, por lo Nque ni siquiera tiene sentido. Pero podría considerar DateTime.Nowuna entrada que haga que esto siga dependiendo del resultado. Si puede asumir un valor realista de DateTime.Now, entonces sí, el programa se repite una cantidad constante de veces.
empuje el
43
El enunciado del problema debe definir qué es N.
Yacoub Massad

Respuestas:

406

La notación Big O en este contexto se utiliza para describir una relación entre el tamaño de la entrada de una función y el número de operaciones que se deben realizar para calcular el resultado de esa entrada.

Su operación no tiene entrada con la que se pueda relacionar la salida, por lo que usar la notación Big O no tiene sentido. El tiempo que tarda la operación es independiente de las entradas de la operación (que es ... ninguna). Dado que no existe una relación entre la entrada y la cantidad de operaciones realizadas, no puede usar Big O para describir esa relación inexistente

Servy
fuente
6
¿Qué hay de O(max(1, 2035 - yearTheProgramIsStarted))?
Bergi
19
@Bergi [En realidad, no [( stackoverflow.com/questions/34048740/… ), no se puede simplemente describir el número de iteraciones del bucle basándose únicamente en el tiempo en que ejecuta el trabajo. Y, por supuesto, combina eso con el hecho de que el usuario puede cambiar el reloj del sistema en cualquier momento a la hora que desee, etc., y aún no tiene una entrada bien formada que pueda relacionarse con precisión con una serie de operaciones necesarias para producir la salida. Diablos, incluso la salida en sí misma no es consistente.
Servicio
23
Se podría argumentar que el estado del sistema (que incluye el reloj) es parte de la entrada del programa. En ese sentido, podría usar la fecha como parámetro de entrada, aunque no explícito. Sin embargo, es extraño.
Connor Clark
9
Para ser más claros, la entrada 'implícita' es el delta entre el 1 de enero de 2035 y hoy.
Connor Clark
6
@Hoten Pero la hora del sistema no es un valor fijo. Esta función no es lo mismo que aceptar DateTimecomo entrada un para la hora de inicio. Como dije anteriormente, el reloj del sistema puede cambiar con el tiempo . Y de nuevo, no puede mapear directamente la entrada quazi que está describiendo a una salida fija. No hay un número conocido de operaciones realizadas para una hora de inicio determinada, o incluso para dos programas que siempre obtienen un valor sensible de DateTime.Now, por lo que no puede relacionar los dos a medida que cambia el tiempo, porque ni siquiera puede relacionarlos cuando el tiempo no cambia.
Servicio
88

La notación Big-O significa aproximadamente 'dada una operación en una cantidad de trabajo, N, ¿cuánto tiempo de cálculo, proporcional a N, toma el algoritmo?'. Por ejemplo, ordenar una matriz de tamaño N puede tomar N ^ 2, Nlog (N), etc.

Esto no tiene una cantidad de datos de entrada sobre los que actuar. Entonces no lo es O(anything).

Peor aún; esto no es técnicamente un algoritmo. Un algoritmo es un método para calcular el valor de una función matemática; las funciones matemáticas son un mapeo de una entrada a una salida. Dado que esto no toma ninguna entrada y no devuelve nada, no es una función, en el sentido matemático. De wikipedia:

Un algoritmo es un método eficaz que se puede expresar en una cantidad finita de espacio y tiempo y en un lenguaje formal bien definido para calcular una función. Comenzando desde un estado inicial y una entrada inicial (quizás vacía), las instrucciones describen un cálculo que, cuando se ejecuta, avanza a través de un número finito de estados sucesivos bien definidos, produciendo eventualmente "salida" y terminando en un estado final final.

Lo que esto es, técnicamente, es un sistema de control. De wikipedia;

Un sistema de control es un dispositivo, o conjunto de dispositivos, que administra, ordena, dirige o regula el comportamiento de otros dispositivos o sistemas.

Para las personas que desean una respuesta más detallada sobre la diferencia entre funciones matemáticas y algoritmos, y las capacidades más poderosas de las computadoras para hacer cosas con efectos secundarios como salida de consola, mostrar gráficos o controlar robots, lea este documento en el Fuerte hipótesis de Church-Turing

Resumen

La visión clásica de la computación posiciona la computación como una transformación de caja cerrada de entradas (números racionales o cadenas finitas) a salidas. Según la visión interactiva de la computación, la computación es un proceso interactivo continuo en lugar de una transformación basada en funciones de una entrada a una salida. Específicamente, la comunicación con el mundo exterior ocurre durante el cálculo, no antes ni después. Este enfoque cambia radicalmente nuestra comprensión de qué es la computación y cómo se modela.

La aceptación de la interacción como un nuevo paradigma se ve obstaculizada por la Strong Church-Turing Thesis (SCT), la creencia generalizada de que las máquinas de Turing (TM) capturan todos los cálculos, por lo que los modelos de computación más expresivos que las TM son imposibles. En este artículo, mostramos que SCT reinterpreta la Tesis original de Church-Turing (CTT) de una manera que Turing nunca pretendió; su equivalencia comúnmente asumida con el original es un mito. Identificamos y analizamos las razones históricas de la creencia generalizada en la SCT. Solo aceptando que es falso podemos comenzar a adoptar la interacción como un paradigma alternativo de computación

Steve Cooper
fuente
No es necesario que sea una secuencia. Es solo una entrada de datos, y la notación landau describe el tiempo de ejecución en relación con algunas métricas de esos datos, generalmente algo relacionado con el tamaño.
Bergi
@Bergi: sí, ¡ve tu punto! En realidad, solo estoy haciendo una aproximación, pero sí, si puede medir la cantidad de trabajo por hacer y la cantidad de pasos necesarios para llegar allí, big-o refleja la relación de esas dos medidas. ¿Cerca?
Steve Cooper
@kapep: no es una función pura porque es un método vacío, pero si contamos la salida de la consola, sigue siendo aleatorio; podría generar cualquiera de {"¡Hola, mundo!", "Todavía no es el momento de imprimir el saludo ... \ n¡Hola, mundo!", "Todavía no es el momento de imprimir el saludo ... Todavía no es el momento de imprimir el hola ... \ n¡Hola, mundo! ", ...}
Steve Cooper
1
¿Imprimir en stdout no es una salida?
rpax
4
@rpax No matemáticamente, no. Una función es una traducción invariable de entradas a salidas; por ejemplo, 'cuadrado' es la función que siempre devuelve 9 si ingresa 3. Un método c # es solo una función matemática si una llamada con los mismos parámetros siempre da el mismo valor de retorno. De lo contrario, si tiene efectos secundarios como escribir en la consola, mostrar gráficos, asignar memoria, esas no son funciones matemáticas. (Voy a agregar un enlace a mi respuesta que entra en detalles insoportables :))
Steve Cooper
41

No, su código tiene una complejidad de tiempo de O(2^|<DeltaTime>|),

Para una correcta codificación de la hora actual.
Por favor, primero déjame disculparme por mi inglés.

Qué es y cómo funciona Big O en CS

La notación Big O no se utiliza para vincular la entrada de un programa con su tiempo de ejecución .
La notación Big O es, dejando atrás el rigor, una forma de expresar la relación asintótica de dos cantidades .

En el caso del análisis de algoritmos, estas dos cantidades no son la entrada (para lo cual primero se debe tener una función de "medida") y el tiempo de ejecución.
Son la longitud de la codificación de una instancia del problema 1 y una métrica de interés.

Las métricas de uso común son

  1. El número de pasos necesarios para completar el algoritmo en un modelo de cálculo dado.
  2. El espacio requerido, si existe tal concepto, por el modelo de computación.

Se asume implícitamente una TM como modelo, de modo que el primer punto se traduce en el número de aplicaciones de la función de transición 2 , es decir, "pasos", y el segundo traduce el número de celdas de cinta diferentes escritas al menos una vez .

¿También a menudo se asume implícitamente que podemos usar una codificación relacionada polinomialmente en lugar de la original, por ejemplo, una función que busca una matriz de principio a fin tiene O(n)complejidad a pesar del hecho de que una codificación de una instancia de dicha matriz debe tener una longitud de n*b+(n-1)donde bes el número (constante) de símbolos de cada elemento. Esto se debe a que bse considera una constante del modelo de cálculo y, por lo tanto, la expresión anterior y nson asintóticamente iguales.

Esto también explica por qué un algoritmo como Trial Division es un algoritmo exponencial a pesar de ser esencialmente un for(i=2; i<=sqr(N); i++)algoritmo similar 3 .

Mira esto .

Esto también significa que la notación O grande puede usar tantos parámetros como sea necesario para describir el problema, ¿no es inusual tener un parámetro k para algunos algoritmos?

Así que no se trata de la "entrada" o de que "no hay entrada".

Estudio de caso ahora

La notación Big O no cuestiona su algoritmo, solo asume que sabe lo que está haciendo. Es esencialmente una herramienta aplicable en todas partes, incluso en algoritmos que pueden ser deliberadamente engañosos (como el suyo).

Para resolver su problema, utilizó la fecha actual y una fecha futura, por lo que deben ser parte del problema de alguna manera; en pocas palabras: son parte de la instancia del problema.

Específicamente la instancia es:

<DeltaTime>

Donde el <>significa cualquier codificación, no patológica, de elección.

Consulte a continuación para obtener aclaraciones muy importantes .

Entonces, su gran tiempo de complejidad O es justo O(2^|<DeltaTime>|), porque realiza una serie de iteraciones que dependen del valor del tiempo actual. No tiene sentido poner otras constantes numéricas ya que la notación asintótica es útil ya que elimina constantes (por ejemplo, el uso de no O(10^|<DeltaTime>|*any_time_unit)tiene sentido).

Donde esta la parte complicada

Hicimos una suposición importante arriba: que el modelo de cálculo reifica 5 el tiempo, y por tiempo me refiero al tiempo físico (¿real?). No existe tal concepto en el modelo computacional estándar, una MT no conoce el tiempo, vinculamos el tiempo con el número de pasos porque así es como funciona nuestra realidad 4 .

En su modelo, sin embargo, el tiempo es parte del cálculo, puede usar la terminología de personas funcionales diciendo que Main no es puro, pero el concepto es el mismo.

Para entender esto, uno debe tener en cuenta que nada impide que el Framework use un tiempo falso que se ejecuta dos, cinco, diez veces más rápido que el tiempo físico. De esta manera, su código se ejecutará en "la mitad", "una quinta parte", "una décima parte" del "tiempo".

Esta reflexión es importante para elegir la codificación de <DeltaTime>, esta es esencialmente una forma condensada de escribir <(CurrentTime, TimeInFuture)>. Dado que el tiempo no existe a priori, la codificación de CurrentTime podría muy bien ser la palabra Now (o cualquier otra opción) el día anterior podría codificarse como Yesterday , rompiendo la suposición de que la duración de la codificación aumenta como el tiempo físico avanza (y el de DeltaTime disminuye)

Tenemos que modelar correctamente el tiempo en nuestro modelo computacional para hacer algo útil.

La única opción segura que podemos hacer es codificar marcas de tiempo con longitudes crecientes (pero sin usar unario) a medida que avanza el tiempo físico. Esta es la única propiedad verdadera del tiempo que necesitamos y la que la codificación necesita capturar. Es solo con este tipo de codificación que a su algoritmo se le puede dar una complejidad de tiempo.

Su confusión, si la hay, surge del hecho de que la palabra tiempo en las frases "¿Cuál es su complejidad temporal ?" y '¿Cuánto tiempo llevará?' significa cosas muy muy diferentes

Lamentablemente, la terminología usa las mismas palabras, pero puedes intentar usar "complejidad de pasos" en tu cabeza y volver a hacerte tu pregunta, espero que te ayude a entender que la respuesta realmente es ^ _ ^


1 Esto también explica la necesidad de un enfoque asintótico, ya que cada instancia tiene una longitud diferente, pero no arbitraria.
2 Espero estar usando el término en inglés correcto aquí.
3 También es por eso que a menudo encontramos log(log(n))términos en matemáticas.
4 Id est, un paso debe ocupar un intervalo de tiempo finito, pero no nulo, ni desconectado.
5 Esto significa que el modo computacional como conocimiento del tiempo físico en él, es decir, puede expresarlo con sus términos. Una analogía es cómo funcionan los genéricos en el marco .NET.

Yuni Mj
fuente
3
"Así que tu tiempo de ejecución de la gran O es simplemente" ... Estoy seguro de que te refieres a 'complejidad de la gran O' ?. Además, todavía podemos simplemente llamar a 'deltaTime' nuestro 'n' correcto ... así que dices O (2 ^ N) algo así como la complejidad del algoritmo de Fibonacci. ¿Cómo llegaste al "2 ^"?
Ross
@Ross, gracias por el punto. Vine con 2 por costumbre para trabajar con números binarios. El punto es que los pasos son lineales con la longitud de la representación del número. La base real no es realmente importante y varía según la codificación específica. Es pseudo lineal .
Yuni Mj
Lo siento, pero ¿podría explicar más en su respuesta cómo llegó a la conclusión de que la complejidad es O(2^n)? No está claro para principiantes.
Arturo Torres Sánchez
2
@YuniMj Si bien tu razonamiento no es técnicamente incorrecto, creo que al insistir en medir el tamaño de en DeltaTimelugar de su valor , solo estás agregando confusión adicional. Por ejemplo, pero ese razonamiento, ningún algoritmo de clasificación óptimo tiene complejidad de tiempo $ O (n \ cdot log n) $. ¿Por qué? Debido a que solo puede ordenar una cantidad finita de objetos distinguibles, en cuyo caso siempre puede usar la clasificación de cubos para ordenar en $ O (n) $. O el tamaño de su objeto es ilimitado, en cuyo caso $ O (n \ cdot log n) $ no se mantendrá, ya que una sola comparación ya no tendrá tiempo constante ...
fgp
1
FWIW O (2 ^ n)! = O (10 ^ n) stackoverflow.com/questions/19081673/…
Nathan FD
29

Aunque hay un montón de buenas respuestas aquí, permítanme reformularlas un poco.

La notación Big-O existe para describir funciones . Cuando se aplica al análisis de algoritmos, esto requiere que primero definamos alguna característica de este algoritmo en términos de una función . La opción común es considerar el número de pasos en función del tamaño de entrada . Como se señaló en otras respuestas, crear tal función en su caso parece extraño, porque no hay una "entrada" claramente definida. Sin embargo, todavía podemos intentar hacerlo:

  • Podemos considerar su algoritmo como una función constante que toma cualquier entrada de cualquier tamaño, la ignora, espera una cantidad fija de tiempo y finaliza. En este caso, su tiempo de ejecución es f (n) = const , y es un algoritmo de tiempo O (1). Esto es lo que esperabas escuchar, ¿verdad? Sí, técnicamente es un algoritmo O (1) .
  • Podemos considerar TwentyYearsLatercomo el parámetro de interés similar al "tamaño de entrada". En este caso, el tiempo de ejecución es f (n) = (nx) donde x es el "momento actual" en el momento de la invocación. Visto de esta manera, es un algoritmo de tiempo O (n). Espere este contraargumento cada vez que vaya mostrando su algoritmo técnico O (1) a otras personas.
  • Oh, pero espere, si k =TwentyYearsLater es la entrada, entonces su tamaño n es, en realidad, el número de bits necesarios para representarlo, es decir, n = log (k) . La dependencia entre el tamaño de la entrada n y el tiempo de ejecución es, por lo tanto, f (n) = 2 ^ n - x . ¡Parece que su algoritmo se ha vuelto exponencialmente lento! Ugh.
  • Otra entrada al programa es, de hecho, el flujo de respuestas dadas por el sistema operativo a la secuencia de DateTime.Nowinvocaciones en el bucle. De hecho, podemos imaginar que toda esta secuencia se proporciona como entrada en el momento en que ejecutamos el programa. Entonces se puede considerar que el tiempo de ejecución depende de la propiedad de esta secuencia, es decir, su longitud hasta el primer TwentyYearsLaterelemento. En este caso, el tiempo de ejecución es nuevamente f (n) = ny el algoritmo es O (n) .

Pero, de nuevo, en su pregunta ni siquiera dijo que estaba interesado en el tiempo de ejecución. ¿Y si te refieres al uso de la memoria? Dependiendo de cómo modele la situación, puede decir que el algoritmo es O (1) -memory o, quizás, O (n) -memory (si la implementación de DateTime.Nowrequiere realizar un seguimiento de toda la secuencia de invocación de alguna manera).

Y si su objetivo era llegar a algo absurdo, ¿por qué no va con todo y dice que está interesado en cómo el tamaño del código del algoritmo en píxeles en la pantalla depende del nivel de zoom elegido? Esto podría ser algo como f (zoom) = 1 / zoom y puedes declarar con orgullo que tu algoritmo tiene un tamaño de píxel de O (1 / n) .

KT.
fuente
+1. Creo que el "flujo de respuestas dado por el sistema operativo a la secuencia de DateTime.Nowinvocaciones" es la entrada real aquí. Pero creo que la conclusión no debería ser que sea O (n), sino O (k), donde k es la longitud hasta el primer TwentyYearsLaterelemento.
justo la mitad del
7
Esta es la mejor respuesta hasta ahora: para que Big O sea significativo, debe aplicar semánticas / suposiciones matemáticas a la implementación física (esencialmente definiendo un modelo matemático para el programa con una definición significativa de "entrada"). En este sentido, la complejidad del "programa" depende de la semántica que aplique; si asume que N es la diferencia de tiempo que escala linealmente con el número de operaciones, es O (n). Si asume un número fijo de operaciones como resultado de un período de tiempo fijo, es O (1).
Ant P
21

Tengo que estar un poco en desacuerdo con Servy. Hay una entrada para este programa, incluso si no es obvia, y ese es el momento del sistema. Esto podría ser un tecnicismo que no pretendía, pero su TwentyYearsFromNowvariable no está a veinte años del tiempo del sistema ahora , está asignada estáticamente al 1 de enero de 2035.

Entonces, si toma este código y lo ejecuta en una máquina que tiene una hora del sistema del 1 de enero de 1970, tardará 65 años en completarse, independientemente de lo rápido que sea la computadora (puede haber alguna variación si su reloj es defectuoso ). Si toma este código y lo ejecuta en una máquina que tiene una hora de sistema del 2 de enero de 2035, se completará casi instantáneamente.

Yo diría que su entrada,, nes January 1st, 2035 - DateTime.Now, y es O (n).

Luego también está la cuestión del número de operaciones. Algunas personas han notado que las computadoras más rápidas alcanzarán el ciclo más rápido, lo que provocará más operaciones, pero eso es irrelevante. Cuando trabajamos con notación Big-O, no consideramos la velocidad del procesador o el número exacto de operaciones. Si tomó este algoritmo y lo ejecutó en una computadora, y luego lo ejecutó nuevamente, pero durante 10 veces más en la misma computadora, esperaría que la cantidad de operaciones crezca en el mismo factor de 10 veces.

En cuanto a esto:

Estoy pensando en usar el fragmento de código [código redactado] como un bucle ocupado para ponerlo como una broma cada vez que alguien pide un algoritmo de cierta complejidad. ¿Sería esto correcto?

No en realidad no. Otras respuestas han cubierto esto, así que solo quería mencionarlo. Por lo general, no puede correlacionar los años de ejecución con ninguna notación de O grande. P.ej. No hay forma de decir 20 años de ejecución = O (n ^ 87) o cualquier otra cosa para el caso. Incluso en el algoritmo que proporcionó, podría cambiar el TwentyYearsFromNowaño 20110, 75699436 o 123456789 y el gran O sigue siendo O (n).

Shaz
fuente
7
El tiempo no es una entrada para la función, es un estado en constante cambio que se observa durante la ejecución del método. El reloj del sistema incluso se puede cambiar mientras se ejecuta la función . Para que Big O sea significativo, también necesitaría que cada entrada corresponda 1-1 con un valor de salida, así como una serie de operaciones necesarias para calcularlo. Para esta operación, la salida ni siquiera es consistente para la misma entrada (de hecho, varía enormemente ), además de que el número de operaciones realizadas también varía enormemente.
Servicio
When working with big-O notation, we don't consider the speed of the processor or the exact number of operations.Ésta es una declaración falsa. Prácticamente cualquier operación sensata de la que intente calcular el valor de Big O no cambiará la cantidad de operaciones realizadas en función del hardware, pero esta sí lo hace . Big O es solo una forma de relacionar el número de operaciones con el tamaño de la entrada. Para la mayoría de las operaciones, es independiente del hardware del sistema. En este caso no lo es .
Servicio
If you took this algorithm and ran it on a computer, and then ran it again but for 10x longer on the same computer, you would expect the number of operations to grow by the same factor of 10x.Esa también es una declaración falsa. El entorno no alterará necesariamente el número de operaciones en el bucle de forma lineal. Por ejemplo, podría haber otros programas en la computadora que usen más o menos tiempo de CPU en diferentes momentos, cambiando el tiempo que se le da a esta aplicación constantemente a lo largo del tiempo.
Servicio
Estoy con @Servy en este caso, pero por una razón ligeramente diferente. La función principal no toma parámetros y no devuelve ninguna entrada. Es una función de nil => nil, si lo desea. No importa la hora, todavía no devuelve nada.
Steve Cooper
1
Si usamos esta definición: "En matemáticas, una función es una relación entre un conjunto de entradas y un conjunto de salidas permitidas con la propiedad de que cada entrada está relacionada con exactamente una salida". (wikipedia) - y estamos contando la salida de la consola como 'la salida de la función', esto varía, se alarga en una computadora más rápida, porque escribirá "" Todavía no es el momento de imprimir el saludo ... "" más a menudo.
Steve Cooper
13

El análisis Big-O se ocupa de la cantidad de procesamiento involucrado a medida que la cantidad de datos que se procesan aumenta sin límite.

Aquí, en realidad solo se trata de un único objeto de tamaño fijo. Como tal, la aplicación del análisis big-O depende en gran medida (¿principalmente?) De cómo defina sus términos.

Por ejemplo, podría referirse a la impresión de resultados en general e imponer una espera tan larga que cualquier cantidad razonable de datos se imprimiría / se imprimirá precisamente en el mismo período de tiempo. Sin embargo, también debe agregar un poco más en forma de definiciones un tanto inusuales (si no totalmente erróneas) para llegar muy lejos; en particular, el análisis de big-O generalmente se define en términos de la cantidad de operaciones fundamentales necesarias para llevar a cabo un análisis. tarea particular (pero tenga en cuenta que la complejidad también se puede considerar en términos de cosas como el uso de memoria, no solo el uso de CPU / operaciones realizadas).

Sin embargo, la cantidad de operaciones fundamentales generalmente se traduce bastante cerca del tiempo que se toma, por lo que no es una exageración tratar las dos como sinónimos. Desafortunadamente, sin embargo, todavía estamos atrapados con esa otra parte: la cantidad de datos que se procesan aumenta sin límite. Siendo ese el caso, ningún retraso fijo que pueda imponer realmente funcionará. Para equiparar O (1) con O (N), tendría que imponer un retraso infinito para que cualquier cantidad fija de datos tardara una eternidad en imprimirse, tal como lo haría una cantidad infinita de datos.

Jerry Coffin
fuente
10

big-O relativo a qué?

Pareces intuir que twentyYearsLateres una "entrada". Si de hecho escribiste tu función como

void helloWorld(int years) {
   // ...
}

Sería O (N) donde N = años (o simplemente decir O(years)).

Yo diría que su algoritmo es O (N) en relación con cualquier número que escriba en la línea de código que comienza twentyYearsLater =. Pero la gente generalmente no considera los números en el código fuente real como entrada. Pueden considerar la entrada de la línea de comandos como la entrada, o la entrada de la firma de la función como la entrada, pero lo más probable es que no el código fuente en sí. Eso es lo que está discutiendo con su amigo: ¿es esta la "entrada"? Configura su código de manera que intuitivamente parezca una entrada, y definitivamente puede preguntar su gran tiempo de ejecución O con respecto al número N en la línea 6 de su programa, pero si usa una opción no predeterminada como entrada, realmente necesita ser explícito al respecto.

Pero si considera que la entrada es algo más habitual, como la línea de comando o la entrada a la función, no hay ninguna salida y la función es O (1). Se necesitan veinte años, pero como big-O no cambia hasta un múltiplo constante, O (1) = O (veinte años).

Pregunta similar: cuál es el tiempo de ejecución de:

void sortArrayOfSizeTenMillion(int[] array)

Suponiendo que hace lo que dice y la entrada es válida, y el algoritmo aprovecha una clasificación rápida o una clasificación de burbujas o cualquier cosa razonable, es O (1).

djechlin
fuente
Codificar la entrada no significa que la entrada desaparezca. Tampoco lo son la clasificación rápida y la clasificación de burbujas de O (1) complejidad de tiempo en ningún caso. bigocheatsheet.com
Theo Brinkman
@TheoBrinkman Si quieres ser técnico, en un modelo de máquina de Turing, codificar lo que piensas de la entrada, en la máquina de Turing, lo convierte, por definición, no en la entrada. La máquina de Turing funcionará en un tiempo constante independientemente de la entrada real que tenga. En cierto sentido, no está ejecutando una "clasificación de burbujas", ya que no clasifica nada, sino que opera en su propia representación, sin embargo, en términos no técnicos, por supuesto, podría describir el algoritmo como una clasificación de burbujas.
djechlin
En términos igualmente "no técnicos", podría describir el algoritmo en cuestión como un puente colgante.
Theo Brinkman
@TheoBrinkman no, no podrías. Eso no tendría sentido para nadie.
djechlin
Tiene tanto sentido como describirlo como una especie de burbuja O (1).
Theo Brinkman
8

Este "algoritmo" se describe correctamente como O (1) o tiempo constante. Se ha argumentado que no hay entrada para este programa, por lo tanto, no hay N para analizar en términos de Big Oh. No estoy de acuerdo con que no haya entrada. Cuando esto se compila en un ejecutable y se invoca, el usuario puede especificar cualquier entrada de longitud arbitraria. Esa longitud de entrada es N.

El programa simplemente ignora la entrada (de cualquier longitud), por lo que el tiempo necesario (o el número de instrucciones de la máquina ejecutadas) es el mismo independientemente de la longitud de la entrada (dado el entorno fijo = hora de inicio + hardware), por lo tanto O (1 ).

waldol1
fuente
Pero la cantidad de operaciones no es necesariamente consistente, incluso con la misma hora de inicio y hardware. Además de eso, para reclamar un algoritmo O (1), la salida tendría que ser siempre constante, y no lo es, variará enormemente según la hora de inicio y el hardware. También podría ser infinito muy fácilmente, lo que ciertamente no es constante. No existe relación entre la entrada que ha definido y el número de operaciones realizadas. Eso no es constante, es simplemente indefinido. No se puede nombrar un número finito y saber que siempre habrá menos operaciones que eso.
Servicio
El tiempo real máximo que llevará es de 20 años. Si lo iniciamos en el futuro, sí, llevará más tiempo. Supongamos que hay un límite inferior finito en la cantidad de tiempo que tarda una iteración de bucle y que estamos ejecutando en hardware serie. Luego, puedo limitar el número de veces que se ejecutará el ciclo, lo que significa que todo el cálculo puede estar limitado por una función constante, sin importar el tamaño de la entrada ignorada.
waldol1
Let's suppose that there is a finite lower bound on the amount of time a loop iteration takesEsa es una suposición falsa. El programa puede ejecutarse para siempre. Todo lo que tengo que hacer es configurar el reloj de mi sistema en 50 años a partir de ahora, iniciarlo y nunca terminará. O podría seguir haciendo retroceder el reloj más rápido de lo que avanza, o ponerlo en marcha en un punto indeterminado del pasado . Simplemente, no puede asumir que existe un límite inferior en cuanto a la duración del programa; puede funcionar para siempre. Pero, incluso si tomamos su suposición (falsa) como verdadera, aún no puede relacionar el número de operaciones realizadas con la entrada.
Servicio
Una iteración de un solo ciclo lleva una cantidad de tiempo finita. Podría ser posible que se ejecute un número infinito de veces, pero cada una debe ser aproximadamente constante. No veo ningún problema con esa suposición.
waldol1
Según esa lógica [completamente incorrecta], cada algoritmo es siempre O (1) porque cada operación individual es siempre constante. Simplemente estás demostrando que ni siquiera sabes qué es Big O. Es una herramienta para (en contexto) describir la relación entre el tamaño de la entrada y el número de operaciones relevantes realizadas. O (1) significa que hay un número constante de operaciones realizadas independientemente de la entrada. Aquí no hay un número constante de operaciones realizadas independientemente de la entrada, hay operaciones potencialmente infinitas realizadas, ¡infinito! = Constante.
Servicio
6

Una cosa que me sorprende no se ha mencionado todavía: ¡la notación Big-O es un límite superior!

El problema que todos han notado es que no hay una N que describa las entradas al algoritmo, por lo que no hay nada con qué hacer un análisis de O grande. Sin embargo, esto se mitiga fácilmente con algunos trucos básicos, como aceptar int ne imprimir las nhoras de "Hola mundo" . Eso evitaría esa queja y volvería a la pregunta real de cómo funciona esa DateTimemonstruosidad.

No hay garantía real de que el ciclo while terminará alguna vez. Nos gusta pensar que tiene que hacerlo en algún momento, pero considere que DateTime.nowdevuelve la fecha y hora del sistema . En realidad, no hay garantía de que esto esté aumentando monótonamente. Es posible que algún mono entrenado patológicamente cambie constantemente la fecha y la hora del sistema hasta el 21 de octubre de 2015 a las 12:00:00 UTC hasta que alguien le dé al mono unos zapatos de ajuste automático y un hoverboard. ¡Este bucle puede durar una cantidad infinita de tiempo!

Cuando realmente profundiza en la definición matemática de notaciones con gran O, son límites superiores. Demuestran el peor de los casos, por improbable que sea. El peor escenario * aquí es un tiempo de ejecución infinito, por lo que nos vemos obligados a declarar que no hay una notación O grande para describir la complejidad del tiempo de ejecución de este algoritmo. No existe, al igual que el 1/0 no existe.

* Editar: de mi discusión con KT, no siempre es válido suponer que el escenario que estamos modelando con la notación Big-O es el peor de los casos. En la mayoría de los casos, si un individuo no especifica qué caso estamos usando, su intención es explorar el peor de los casos. Sin embargo, puede hacer un análisis de complejidad big-O en el mejor tiempo de ejecución.

Cort Ammon
fuente
2
O es, en cierto sentido, un "límite superior", de hecho, pero no significa que solo pueda hablar de "complejidad en el peor de los casos" usando la notación O. Complejidad esperada, complejidad en el mejor de los casos, cualquier otra propiedad funcional, todas ellas pueden discutirse en términos de sus límites O.
KT.
La complejidad del mejor caso de @KY se llama little-o, y la complejidad esperada es big-theta. big-o es siempre el peor caso de complejidad, según su definición matemática.
Cort Ammon
No, te equivocas aquí. Vuelva a verificar las definiciones.
KT.
@KT Está bien, los volveré a revisar. Vuelve a revisarlos también. en.wikipedia.org/wiki/Big_O_notation Está bajo las notaciones Familia de Bachmann – Landau
Cort Ammon
Supongo que podrías hacer algo loco como tomar una función fy declarar que la función ges la misma que f, pero con un dominio restringido para incluir solo fel mejor caso, y luego hacer grande g, pero comienza a sonar degenerado cuando lo haces ese.
Cort Ammon
5

La complejidad se utiliza para medir la "potencia" computacional en términos de tiempo / espacio. La notación Big O se usa para comparar qué problemas son "computables" o "no computables" y también para comparar qué soluciones -algoritmos- son mejores que otras. Como tal, puede dividir cualquier algoritmo en dos categorías: los que se pueden resolver en tiempo polinómico y los que no.

Problemas como el tamiz de erathostene son O (n ^ exp) y, por lo tanto, se pueden resolver para valores pequeños de n. Son computables, pero no en tiempo polinomial (NP) y, por lo tanto, cuando se le pregunta si un número dado es primo o no, la respuesta depende de la magnitud de dicho número. Además, la complejidad no depende del hardware, por lo que tener ordenadores más rápidos no cambia nada ...

Hello World no es un algoritmo y, como tal, no tiene sentido intentar determinar su complejidad, que no es ninguna. Un algoritmo simple puede ser algo como: dado un número aleatorio, determine si es par o impar. Ahora bien, ¿importa que el número dado tenga 500 dígitos? No, porque solo tienes que comprobar si el último dígito es par o impar. Un algoritmo más complejo sería determinar si un número dado se divide uniformemente entre 3. Aunque algunos números son "fáciles" de calcular, otros son "difíciles" y esto se debe a su magnitud: compare el tiempo que lleva determinar el remanente entre un número de un dígito y otro de 500 dígitos.

Un caso más complejo sería decodificar un texto. Tiene una serie aparentemente aleatoria de símbolos que también sabe que están transmitiendo un mensaje para quienes tienen la clave de descifrado. Digamos que el remitente usó la tecla de la izquierda y su Hola mundo leería: Gwkki Qieks. La solución "martillo grande, sin cerebro" produciría todas las combinaciones para esas letras: desde Aaaa hasta Zzzz y luego buscaría en un diccionario de palabras para identificar qué palabras son válidas y compartir las dos letras comunes en la cifra (i, k) en la misma posición. ¡Esta función de transformación es lo que mide Big O!

Turing
fuente
4

La mayoría de la gente parece perder dos cosas muy importantes.

  1. El programa hace tener una entrada. Es la fecha / hora codificada de forma rígida con la que se compara la hora del sistema. Las entradas están bajo el control de la persona que ejecuta el algoritmo y la hora del sistema no. Lo único que puede controlar la persona que ejecuta este programa es la fecha / hora que ha codificado en la comparación.

  2. El programa varía según el valor de entrada , pero no el tamaño del conjunto de entrada , que es de lo que se ocupa la notación O grande.

Por lo tanto, es indeterminado, y la mejor notación 'gran-O' para este programa probablemente sería O (nulo), o posiblemente O (NaN).

Theo Brinkman
fuente
1
(2) está completamente mal. Normalmente se considera la "longitud de la entrada". Para una lista o matriz de objetos de tamaño fijo (como enteros), de hecho será el tamaño del conjunto. Para factorizar un número como 1395195191600333 será la longitud de su representación binaria (o decimal, etc.), es decir, el número de dígitos. Como se indicó, su definición en (2) prohíbe el uso de big-O para discutir la complejidad de "findPrimeFactors (int num)", que la mayoría de los criptógrafos objetarán.
djechlin
4

Todos han señalado correctamente que no define N , pero la respuesta es no bajo la interpretación más razonable. Si N es la longitud de la cadena que estamos imprimiendo y "¡hola, mundo!" es solo un ejemplo, como podríamos inferir de la descripción de esto como un algoritmo "para" hello, world!, entonces el algoritmo es O ( N ), porque es posible que tenga una cadena de salida que tarde treinta, cuarenta o cincuenta años en imprimirse, y Solo agrego un tiempo constante a eso. O ( kN + c ) ∈ O ( N ).

Apéndice:

Para mi sorpresa, alguien está cuestionando esto. Recuerde las definiciones de gran O y gran Θ. Suponga que tenemos un algoritmo que espera una cantidad constante de tiempo cy luego imprime un mensaje de longitud N en tiempo lineal. (Esta es una generalización de la muestra de código original). Digamos arbitrariamente que esperamos veinte años para comenzar a imprimir, y que imprimir un billón de caracteres lleva otros veinte años. Sea c = 20 y k = 10¹², por ejemplo, pero cualquier número real positivo servirá. Esa es una tasa de d = c / k (en este caso 2 × 10⁻¹¹) años por carácter, por lo que nuestro tiempo de ejecución f ( N ) es asintóticamentedN + c años. Siempre que N > k , dN = c / k N > c . Por lo tanto, dN < dN + c = f ( N ) <2 dN para todo N > k , y f ( N ) ∈ Θ ( N ). QED

Davislor
fuente
Donde tenemos N = 13.
djechlin
Pero no solo imprime "Hola mundo", sino que imprime un número desconocido de líneas "Todavía no es el momento". Además, Big O no se usa realmente para comparar el tamaño de la entrada con el tamaño de la salida, generalmente se usa para comparar el tamaño de la entrada con el número de operaciones o la cantidad de memoria utilizada.
Servicio
@Servy Es una memoria constante, pero estaba limitando implícitamente el tiempo de ejecución. El tamaño de la salida también es O ( N ), para una cadena arbitraria: la cadena que imprimimos cuando sea el momento podría ser arbitrariamente grande, incluso en comparación con veinte años de mensajes por favor espere.
Davislor
@Servy He editado para aclarar que, no, N aquí no es el tamaño de la salida. No estoy seguro de cómo di esa impresión, pero eliminaré cualquier ambigüedad.
Davislor
1
Entonces, si asume que el programa toma una entrada, cuando no lo hace, que la salida puede ser arbitrariamente grande, cuando no puede, que el ciclo no hace nada, cuando lo hace, y que la salida está relacionada con la entrada, cuando no lo es, entonces sí, el programa es lineal. Por supuesto, cada una de esas suposiciones es completamente falsa, por lo que la conclusión que ha extraído de ellas no es válida. Si puede demostrar su punto sin hacer suposiciones falsas, entonces significaría algo.
Servicio
4

Creo que la gente se está volviendo loca porque el código no parece un algoritmo tradicional. Aquí hay una traducción del código que está mejor formada, pero se mantiene fiel al espíritu de la pregunta de OP.

void TrolloWorld(long currentUnixTime, long loopsPerMs){
    long laterUnixTime = 2051222400000;  //unix time of 01/01/2035, 00:00:00
    long numLoops = (laterUnixTime-currentUnixTime)*loopsPerMs;

    for (long i=0; i<numLoops; i++){
        print ("It's still not time to print the hello …");
    }
    print("Hello, World!");
}

Las entradas son explícitas, mientras que antes se daban implícitamente en el momento en que se iniciaba el código y por la velocidad del hardware que ejecuta el código. El código es determinista y tiene una salida bien definida para entradas dadas.

Debido a las limitaciones que se imponen a las entradas que podemos proporcionar, existe un límite superior para el número de operaciones que se ejecutarán, por lo que este algoritmo es de hecho O (1).

Nathan FD
fuente
2

En este momento, sí

Este algoritmo tiene una entrada implícita, es decir, el momento en que se inicia el programa. El tiempo de ejecución variará linealmente 1 dependiendo de cuándo se inicie. Durante el año 2035 y después, el ciclo while sale inmediatamente y el programa termina después de operaciones constantes 2 . Entonces se podría decir que el tiempo de ejecución es O(max(2035 - start year, 1))3 . Pero dado que nuestro año de inicio tiene un valor mínimo, el algoritmo nunca tardará más de 20 años en ejecutarse (es decir, un valor constante).

Puede hacer que su algoritmo sea más acorde con su intención definiendo DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);4

1 Esto es válido para el sentido más técnico del tiempo de ejecución medido como número de operaciones porque hay un número máximo de operaciones por unidad de tiempo.
2 Suponiendo que la búsqueda DateTime.Nowes una operación constante, lo cual es razonable.
3 Estoy abusando un poco de la notación O grande aquí porque esta es una función decreciente con respecto a start year, pero podríamos rectificarlo fácilmente expresándolo en términos de years prior to 2035.
4 Entonces, el algoritmo ya no depende de la entrada implícita de la hora de inicio, pero eso no tiene importancia.

Nathan FD
fuente
1

Yo diría que esto es O (n). utilizando http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html como referencia.

¿Qué es Big O?

La notación Big O busca describir la complejidad relativa de un algoritmo al reducir la tasa de crecimiento a los factores clave cuando el factor clave tiende hacia el infinito.

y

El mejor ejemplo de Big-O que se me ocurre es hacer aritmética. Las operaciones aritméticas básicas que aprendimos en la escuela fueron:

adición; sustracción; multiplicación; y división. Cada uno de estos es una operación o un problema. Un método para resolverlos se llama algoritmo.

Por tu ejemplo,

dada la entrada de n = 20 (con unidades años).

el algoritmo es una función matemática f (). donde f () es esperar n años, con cadenas de 'depuración' en el medio. El factor de escala es 1. f () se puede reducir o aumentar cambiando este factor de escala.

para este caso, la salida también es 20 (al cambiar la entrada, la salida cambia linealmente).

esencialmente la función es

f(n) = n*1 = n
    if  n = 20, then 
f(20) = 20 
Ángel Koh
fuente