c# - ¿Es técnicamente un algoritmo O(1) para "Hello World"?

.net algorithm (15)

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 ¹ dependiendo de cuándo se inicie. Durante el año 2035 y posteriores, el ciclo while se cierra inmediatamente y el programa finaliza después de operaciones constantes ² . Entonces se podría decir que el tiempo de ejecución es O(max(2035 - start year, 1)) ³ . 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 4}

¹ 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.
² Suponiendo que la recuperación DateTime.Now es una operación constante, lo cual es razonable.
³ 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 rectificarla fácilmente expresándola en términos de years prior to 2035 .
⁴ Entonces el algoritmo ya no depende de la entrada implícita de la hora de inicio, pero eso no tiene ninguna consecuencia.

¿Sería esto clasificado como un algoritmo O (1) para "Hello, World!" ??

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 poner en broma cada vez que alguien solicita un algoritmo de cierta complejidad. ¿Sería esto correcto?

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

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

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

La notación Big O no se usa para vincular la entrada de un programa con su tiempo de ejecución .
La notación O grande 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 la cual primero 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 ¹ y una métrica de interés.

Las métricas utilizadas comúnmente son

El número de pasos necesarios para completar el algoritmo en un modelo de cálculo dado.
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 ² , es decir, "pasos", y el segundo traduce el número de celdas de cinta diferentes escritas al menos una vez .

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

Esto también explica por qué un algoritmo como la División de Prueba es un algoritmo exponencial a pesar de ser esencialmente un algoritmo ³ for(i=2; i<=sqr(N); i++) .

Mira this .

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 supone que sabe lo que está haciendo. Es esencialmente una herramienta aplicable en todas partes, incluso al algoritmo que puede ser deliberadamente complicado (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 <> significa cualquier codificación de elección no patológica.

Vea abajo para aclaraciones muy importantes .

Por lo tanto, su gran tiempo de complejidad O es solo 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 O(10^|<DeltaTime>|*any_time_unit) tiene sentido).

Donde está la parte difícil

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

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

Para comprender esto, se debe tener en cuenta que nada impide que Framework use un tiempo falso que se ejecute dos, cinco, diez veces más rápido que el tiempo físico. De esta manera, su código se ejecutará en "medio", "un quinto", "un décimo" 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 antes, la codificación de CurrentTime bien podría ser la palabra Ahora (o cualquier otra opción) el día anterior podría codificarse como Ayer , rompiendo el supuesto de que la longitud de la codificación aumenta a medida que aumenta el tiempo físico avanza (y el de DeltaTime disminuye)

Tenemos que modelar adecuadamente 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 aún sin usar unario) a medida que avanza el tiempo físico. Esta es la única propiedad verdadera del tiempo que necesitamos y la que necesita la codificación. Es solo con este tipo de codificación que su algoritmo puede tener 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

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

¹ Esto también explica la necesidad de un enfoque asintótico ya que cada instancia tiene una longitud diferente, pero no arbitraria.
² Espero estar usando el término correcto en inglés aquí.
³ También es por eso que a menudo encontramos términos log(log(n)) en las matemáticas.
⁴ Id est, un paso debe ocupar un intervalo de tiempo finito, pero no nulo, ni conectado.
⁵ 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 .NET Framework.

Creo que la gente está siendo rechazada porque el código no parece un algoritmo tradicional. Aquí hay una traducción del código que está más bien formado, 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 inició el código y en 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).

La complejidad se utiliza para medir la "potencia" computacional en términos de tiempo / espacio. La notación O grande 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: las que se pueden resolver en tiempo polinómico y las 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, simplemente no en tiempo polinómico (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 computadoras más rápidas no cambia nada ...

Hello World no es un algoritmo y, como tal, no tiene sentido intentar determinar su complejidad, que es ninguna. Un algoritmo simple puede ser algo así como: dado un número aleatorio, determinar si es par o impar. Ahora, ¿importa que el número dado tenga 500 dígitos? No, porque solo tiene que verificar si el último dígito es par o impar. Un algoritmo más complejo sería determinar si un número dado se divide equitativamente 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 toma determinar el resto entre un número con un dígito y otro con 500 dígitos.

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

Parece que a la mayoría de las personas les faltan dos cosas muy importantes.

El programa hace tener una entrada. Es la fecha / hora codificada 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 codificaron en la comparación.
El programa varía en función del valor de entrada , pero no del tamaño del conjunto de entrada , que es de lo que se trata la notación big-O.

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

Todos han señalado correctamente que no se 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 demore treinta, cuarenta o cincuenta años en imprimirse, y solo agrega un tiempo constante a eso. O ( kN + c ) ∈ O ( N ).

Apéndice:

Para mi sorpresa, alguien está disputando esto. Recordemos las definiciones de big O y big Θ. Supongamos que tenemos un algoritmo que espera una cantidad constante de tiempo c y luego imprime un mensaje de longitud N en tiempo lineal. (Esta es una generalización del ejemplo 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óticamente dN + c años. Siempre que N > k , dN = c / k N > c . Por lo tanto, dN < dN + c = f ( N ) <2 dN para todos N > k , yf ( N ) ∈ Θ ( N ). QED

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 que hacer con el análisis big-O. Sin embargo, esto se mitiga fácilmente con algunos trucos básicos, como aceptar int n e imprimir n tiempos de "Hola Mundo" . Eso evitaría esa queja y volvería a la verdadera pregunta de cómo funciona esa DateTime monstruosidad.

No hay garantía real de que el ciclo while termine alguna vez. Nos gusta pensar que debe hacerlo en algún momento, pero tenga en cuenta que DateTime.now devuelve la fecha y la hora del sistema . En realidad, no hay garantía de que esto esté aumentando monotónicamente. Es posible que haya algún mono patológicamente entrenado que cambia constantemente la fecha y 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 autoajustables y un hoverboard. ¡Este bucle puede funcionar durante una cantidad de tiempo infinita!

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

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

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 reduciendo la tasa de crecimiento a los factores clave cuando el factor clave tiende hacia el infinito.

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 su ejemplo,

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

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

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

esencialmente la función es

f(n) = n*1 = n if n = 20, then f(20) = 20

Aunque hay un montón de excelentes 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 algunas características 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, encontrar esa 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 el TwentyYearsLater como el parámetro de interés de "tamaño de entrada". En este caso, el tiempo de ejecución es f (n) = (nx) donde x es el "tiempo actual" en el momento de la invocación. Cuando se ve de esta manera, es un algoritmo de tiempo O (n). Espere este contraargumento cada vez que muestre su algoritmo técnicamente O (1) a otras personas.
Ah, pero espera, 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 ny 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, la secuencia de respuestas dadas por el sistema operativo a la secuencia de invocaciones DateTime.Now en el bucle. De hecho, podemos imaginar que toda esta secuencia se proporciona como entrada en el momento en que ejecutamos el programa. Se puede considerar que el tiempo de ejecución depende de la propiedad de esta secuencia, es decir, su longitud hasta el primer elemento TwentyYearsLater . 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. ¿Qué pasa 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, tal vez, O (n) -memory (si la implementación de DateTime.Now requiere realizar un seguimiento de la secuencia de invocación completa por algún motivo).

Y si su objetivo era llegar a algo absurdo, ¿por qué no entra 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 así como f (zoom) = 1 / zoom y puede declarar con orgullo que su algoritmo tiene un tamaño de O (1 / n) -píxel!

Big-O en relación con qué?

Parece estar intuyendo que twentyYearsLater es una "entrada". Si de hecho escribiste tu función como

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

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

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 con 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 entrada o la entrada de firma de función como entrada, pero lo más probable es que no sea el código fuente en sí. Eso es lo que estás discutiendo con tu amigo: ¿es esta la "entrada"? Configura su código de manera que parezca intuitivamente 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 salida en absoluto y la función es O (1). Lleva veinte años, pero dado que big-O no cambia a 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 de burbuja o algo razonable, es O (1).

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

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

Por ejemplo, podría significar imprimir la salida en general e imponer una espera tanto tiempo que cualquier cantidad razonable de datos se imprimiría / se imprimiría exactamente en el mismo período de tiempo. Sin embargo, también debe agregar un poco más en el sentido de definiciones algo inusuales (si no completamente equivocadas) para llegar muy lejos; en particular, el análisis big-O generalmente se define en términos de la cantidad de operaciones fundamentales necesarias para llevar a cabo un tarea particular (pero tenga en cuenta que la complejidad también puede considerarse 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 estrechamente en el tiempo necesario, por lo que no es una gran extensión tratar a los 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 igualar 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.

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 aportes. Cuando esto se compila en un ejecutable y se invoca, el usuario puede especificar cualquier entrada de longitud arbitraria. Esa longitud de entrada es la N.

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

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 para actuar. Entonces no 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 tiene entrada y no devuelve nada, no es una función, en el sentido matemático. De wikipedia:

Un algoritmo es un método efectivo que puede expresarse dentro de 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 finalmente "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 profunda sobre la diferencia entre las funciones matemáticas y los algoritmos, y las capacidades más poderosas de las computadoras para hacer efectos secundarios como la salida de la consola, mostrar gráficos o controlar robots, lea este documento en el Fuerte hipótesis de Turing de la Iglesia

Resumen

La vista clásica de la computación posiciona el cálculo como una transformación de caja cerrada de entradas (números racionales o cadenas finitas) a salidas. Según la vista interactiva de la informática, 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 lo que es el cálculo y cómo se modela.

La aceptación de la interacción como un nuevo paradigma se ve obstaculizada por la Tesis de Turing de la Iglesia Fuerte (SCT), la creencia generalizada de que las Máquinas de Turing (TM) capturan toda la computación, 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 tuvo la intención; su equivalencia comúnmente asumida con el original es un mito. Identificamos y analizamos las razones históricas de la creencia generalizada en SCT. Solo aceptando que es falso podemos comenzar a adoptar la interacción como un paradigma alternativo de cómputo

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

Su operación no tiene entrada con la que pueda relacionarse la salida, por lo que usar la notación Big O no tiene sentido. El tiempo que lleva la operación es independiente de las entradas de la operación (que es ... ninguna). Como no existe una relación entre la entrada y el número de operaciones realizadas, no puede usar Big O para describir esa relación inexistente

Tengo que estar un poco en desacuerdo con Servy. Hay una entrada para este programa, incluso si no es obvio, y ese es el momento del sistema. Esto podría ser un tecnicismo que no había previsto, pero su variable TwentyYearsFromNow 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 la velocidad de la computadora (puede haber alguna variación si su reloj está defectuoso) ) Si toma este código y lo ejecuta en una máquina que tiene una hora del sistema del 2 de enero de 2035, se completará casi al instante.

Yo diría que su entrada, n , es 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, causando 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 el número de operaciones crezca en el mismo factor de 10x.

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 solicita 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 años de ejecución con ninguna notación big-O. P.ej. No hay forma de decir 20 años de ejecución = O (n ^ 87) o cualquier otra cosa. Incluso en el algoritmo que proporcionó, podría cambiar TwentyYearsFromNow al año 20110, 75699436 o 123456789 y el big-O sigue siendo O (n).