Si un algoritmo se ejecuta en tiempo O (N), pero N no excede una constante, ¿puedo decir que el algoritmo se ejecuta en tiempo constante?

Para todos los efectos, es importante entender que depende de si la constante es parte de la entrada o no y si es realmente constante. Describimos algoritmos con respecto al tamaño de la entrada, pero si sabe con certeza que [math] N \ leq c [/ math] donde [math] c [/ math] es una constante positiva independiente de la entrada, entonces puede escribir [matemáticas] N \ en O (c) \ subseteq O (1) [/ matemáticas].

Ahora, algo que debo enfatizar es que si haces algo como esto (palabra clave, me gusta ), puede hacer que tu problema no sea terriblemente interesante la mayor parte del tiempo. Por ejemplo, ¿qué me impide simplemente fijar el tamaño de la entrada entonces? Eso, en muchos casos, tomará un problema interesante con un número infinito de instancias y lo convertirá en uno con un número finito de instancias (o simplemente hará que el problema sea trivial de resolver).

De hecho, hay momentos en los que desearía imponer una constante como esa, por ejemplo, si está diseñando un algoritmo donde sabe que la instancia de ese tamaño tiene una propiedad especial (o dice que la complejidad temporal de su algoritmo fue peor), pero muchas veces incluir esto como una restricción generalmente convierte un problema en uno menos interesante.

Mi punto es que, por lo general, introducir constantes como esa puede parecer muy artificial y no natural hacerlo matemáticamente en muchas situaciones. No sé cuál es realmente su algoritmo, ni cuál es el problema que está estudiando, así que no puedo juzgar más allá de eso. También es importante enfatizar que los algoritmos son matemáticos y no se limitan a su implementación en una computadora. Entonces, usar una excusa como oh, pero mi entrada solo puede ser tan grande en la computadora no es realmente significativa, ya que no dice nada sobre el algoritmo real, eso dice cosas sobre su implementación y las dependencias de la máquina que pueda tener. Ese tipo de excusas tiene sentido cuando se discuten cosas como los algoritmos sensibles a la salida y, por lo general, no se imponen sobre el problema en sí, sino que normalmente se colocan en la experimentación o implementación del algoritmo.

Ahora, si desea que esa constante sea un parámetro real del problema (en realidad no es una constante, pero la trata como si la estuviera solucionando), puede parametrizar el problema y estudiarlo desde un punto de vista de la complejidad parametrizada: Wikipedia.

El orden de complejidad es solo una aproximación de límite superior e inferior, y solo se utiliza para analizar algoritmos para estimar la cantidad de tiempo que tomaría máxima y mínimamente completar una corrida de cómputo.
La clasificación es una de esas cosas que lleva mucho tiempo revisar un conjunto de datos una y otra vez, al igual que los algoritmos para problemas matemáticos numéricos difíciles, como la determinación de factores primos de grandes números o el modelado de redes neuronales, etc.
Por supuesto, cada algoritmo tiene un límite superior dado un límite superior en el número de puntos de datos, pero el punto es que hay formas más eficientes de llegar a los resultados finales que la fuerza bruta intentando cada combinación o permutación posible. Sin embargo, a veces incluso tienes que hacer eso.
Decir que un algoritmo se ejecuta en O (N) es decir que el tiempo que tarda en completarse es directamente proporcional al tamaño del conjunto de datos, como un límite superior. Por lo tanto, la clasificación de 100 elementos debería ser aproximadamente 10 veces más rápida que la clasificación de 1000 elementos, el peor de los casos para ambos.

Los algoritmos de encriptación están diseñados para que le tome O (2 ^ N) tiempo resolver el peor de los casos como su principal razón de ser. En ese caso, querrás que te lleve una eternidad (a menos que tengas las llaves).

N en la notación “Big O” no es una constante, sino un símbolo de un conjunto de datos finitos de N elementos con los que tratar u operaciones que realizar. Comprenda que un algoritmo podría tener muchos, muchos pasos y aún así tener un número Big O bajo. O (NlogN) se considera bastante bueno y generalmente es lo mejor que puede hacer para la mayoría de los algoritmos complejos.
Un algoritmo podría tener 500 pasos y seguir siendo O (N). Una tabla Hash podría tener un millón de entradas y aún tener tiempo de acceso O (logN) . (¡por eso las tablas hash son tan increíbles!)
O (N ^ 2) es normal para ordenar con métodos lineales como doble para bucles o ordenaciones recursivas.
Las bases de datos prueban todo tipo de algoritmos para tratar de acercarse a O (1) para búsquedas y O (N) para la colocación, pero esos son mínimos teóricos, O (logN) para búsquedas y O (NlogN) para la colocación sigue siendo bastante bueno para recuperación general datos.

La búsqueda binaria viene en magra y media en O (log N) . Eso significa que para cada aumento de 10 veces la cantidad de datos, agregará solo log (T) al peor de los casos. 100 artículos toman T = 2, 1000 artículos toman T = 3, 10,000 artículos T = 4….

Comprenda que el análisis del tiempo Big O para algoritmos puede ser útil para comprender los cuellos de botella en los programas y los gráficos de datos complejos, etc., y es un estudio valioso, pero como otros han dicho, generalmente no es una opción qué algoritmo usar, y sin una revisión real del código, realmente no sabes que ahí es donde está la desaceleración.

Las fórmulas matemáticas tienen su propio tiempo Big O dentro del código que se agrega a ese tiempo.
Digamos, por ejemplo, que necesita calcular las raíces cúbicas del cuadrado de un conjunto de 100 números (enteros). ¿Cuál es el orden de tal función?
N: 100

Cuadrar N toma una sola multiplicación por artículo. Si observa el código de máquina para multiplicar, verá que se puede hacer con aproximadamente 8–12 instrucciones de CPU para cualquier número en el conjunto de datos de ints. 12 * 100 = 1200. Muy lineal a medida que el tiempo crece proporcionalmente a una constante fija (C) multiplicada por el tamaño (N) del conjunto de datos a trabajar.
pero C * O (N) = O (CN) = O (N) ( C << N C insignificante para N)) por lo que la multiplicación es ~ O (N) con hardware especial. Usted ve que a medida que N crece exponencialmente, C permanece igual, por lo que se vuelve insignificante para N. O (N) .

Sin embargo, si decidiste que tienes que multiplicar por suma repetida, por alguna razón, eso implicaría agregar cada número a sí mismo la misma cantidad de veces que su valor. Cuanto mayor es el número, más operaciones de suma.
Si el número fuera 100, cuadrarlo requeriría 99 operaciones de suma. 99 es significativo en comparación con 100 (~ 10 ^ 2), por lo que debe tenerlo en cuenta. Eso significa que dado N hay N pasos para cada elemento. Entonces ahora tendría un algoritmo O (N * N) O (N ^ 2).

La raíz del cubo viene después. Eso es más complejo para calcular Big O en. Primero, ¿cómo se hace? Por división O por multiplicación y división. La forma más simple en que puedo pensar en la parte superior de mi cabeza a la 1 de la mañana es hacer una estimación excesiva / insuficiente.

elija un número aleatorio x menos que el orden base 2 de n. Cubicalo.
x ^ 3 = n? tómalo.
y = 2
lazo A:
x ^ 3> n? restar x / y de x. Inténtalo de nuevo.
x ^ 3> n? y = y + 1; ir a

Lazo B:
x ^ 3 x ^ 3 x ^ 3> n? y = y + 1; ir a

repita con (x, y) y continúe hasta X ^ 3 = n con suficientes dígitos para tomar como resultado.
Ahora suponiendo que x ^ 3 es O (N) , para cada elemento en el conjunto de datos, tiene entre N / 2 +2 viajes alrededor del bucle A y lo mismo para el peor caso del bucle B, entonces
para N números cada resultado toma:
N (N + (N / 2 + 2) + (N / 2 + 2) + C) = N (2N + 4 + C) = 2N ^ 2 + 4N + pasos CN.
reducir a 2 (N ^ 2 + (2 + C / 2) N) ==> O (N ^ 2 + N)
Probablemente equivocado, pero esa es la idea.
Entonces, procesar 1000 números de esta manera tomaría más de un millón de pasos.
Pero procesar 10,000 números de esta manera requeriría más de 100 millones de pasos. Un aumento de 10x resulta en un aumento de 100x tiempo para completar. Pero es la raíz cúbica el camino en curso. Podría hacerlo peor: comience con x = 1 y simplemente increméntelo en 1 hasta que x ^ 3 exceda n, luego vaya al siguiente punto decimal …

Entonces, a veces es importante, especialmente con algoritmos de bucle peludos.

TLDR; N puede ser cualquier número; N en sí no es una cantidad fija mayor o menor que cualquier constante .
O (C) = O (1); cualquier O con N en el numerador es de un orden superior a ese.
Incluso O (logN)> O (1).

Sí seguramente. Sin embargo, agregando a Bill Province, creo que es muy beneficioso darse cuenta de que en el mundo práctico nunca se puede encontrar una situación en la que N no esté limitado por una constante.

Tamaño de los números? Por lo general, no más grande que 2 ^ 32 – 1 o 2 ^ 64 – 1 – constantes, y en este caso, en el 99,9% de los casos, tratamos el tamaño de los números como constante. Si no lo hiciéramos, todos los algoritmos tendrían términos adicionales como O (log K) para cualquier suma de números y [math] O (log ^ 2 K) [/ math] o [math] O (log K log log K) [/ matemáticas] para la multiplicación. Casi nunca lo tomamos en cuenta, utilizando el mismo principio sobre el que pregunta: que si un algoritmo (para la suma de números) se ejecuta en O (log K) pero K no excede una constante (2 ^ 32 – 1), entonces esta operación es O (1).

Esto fue fácil, pero ¿qué pasa con el tamaño de la entrada completa, no solo el tamaño de los números? Fácil, a menos que trabaje con algunos algoritmos en línea que pueden olvidar cosas a lo largo de la ejecución, ¡su entrada no excede una constante! Por qué, porque lo ejecutas en una máquina (o conjunto de máquinas) que tiene una cantidad finita de memoria. El tamaño de la memoria en la que trabaja es constante, N no lo excede, estrictamente hablando, ninguno de sus algoritmos se ejecuta en O (1).

Ok, tal vez si, como dije, ese es un algoritmo en línea, el límite de memoria no es suficiente. Pero si realmente queremos … la velocidad con la que puede leer la entrada está limitada por alguna constante. Entonces, si desea saber si N está limitado por una constante, tome esta velocidad, multiplíquela por el momento desde ahora hasta la fecha esperada de la muerte del Sol, a menos que su algoritmo sea tan crucial para la humanidad que salvará una máquina con este algoritmo aún funciona cuando evacua de la Tierra, hay una cantidad constante de lo que puede leer antes, por lo que su algoritmo se ejecuta en O (1).

Bromas aparte, ¿cuál es la conclusión? En todos estos tres casos, desde el punto de vista teórico, cualquiera de sus algoritmos es O (1). En el primer caso, casi siempre queremos tratarlo como O (1), en el segundo y tercer caso definitivamente no queremos. Lo simple de darse cuenta es que, en la práctica, no queremos tratar la complejidad como un objetivo final. Si estamos en informática teórica donde el objetivo es clasificar los problemas por su complejidad y mostrar dependencias entre ellos, la complejidad es el objetivo y entonces cualquier cosa limitada por una constante es de hecho O (1). En el mundo práctico, la razón por la cual la complejidad es una medida útil es que proporciona una muy buena compensación en el sentido de que A) es rápido y fácil de probar B) por lo general ofrece una visión general suficientemente buena de lo bueno que es el algoritmo. Entonces, la forma correcta de ver la complejidad es que le da un muy buen comienzo para discutir qué tan bueno es un algoritmo: debe verlo de la manera “este algoritmo tiene una mejor complejidad, pero …”. La complejidad es el primer paso desde el cual puede determinar fácilmente si necesita decir que ” pero en la práctica esta constante es tan grande que el peor algoritmo es mejor” o necesita decir “de hecho, en estos casos no veo grandes diferencias en constantes, entonces el mejor algoritmo es mejor y vamos con él ”. Ya sea que cuando N esté limitado por una constante, debe decir que tiene un algoritmo O (1) o si debe pretender que N no tiene límites y decir qué es la complejidad real, es una de las cosas que debe decidir durante dicho análisis.

La única forma de responder a esta pregunta es definir qué quiere decir con O (N).

La definición de la notación O grande es la siguiente:

[matemáticas] f (x) = O (g (x)) [/ matemáticas] como x [matemáticas] \ rightarrow \ infty [/ matemáticas]

si y solo si

[matemáticas] | f (x) | \ leq M | g (x) | [/ math] para todos [math] x \ geq x_0 [/ math] para algunos [math] x_0 [/ math] y algunos [math] M [/ math]

Entonces, la respuesta directa a su pregunta, N tiene que ir al infinito para usar la notación [matemática] O (N) [/ matemática]. Para que la notación O grande sea significativa, no puede haber un límite en el tamaño de entrada.

Ahora, por supuesto, podemos modificar un poco el problema para tratar de llegar a lo que estás tratando de implicar. Básicamente, creamos una nueva función que lleva los valores hasta el infinito, pero corta la salida en algún umbral.

Digamos que su función es [matemáticas] h (x) [/ matemáticas] se define de la siguiente manera:

[matemáticas] h (x) = f (x) [/ matemáticas] para [matemáticas] x \ leq x * [/ matemáticas]

[matemáticas] h (x) = f (x *) [/ matemáticas] para [matemáticas] x> x * [/ matemáticas]

En ese caso, la función modificada [matemática] h (x) [/ matemática] es [matemática] O (1) [/ matemática].

La forma en que esto se traduce en su algoritmo es que no puede decir que su algoritmo es O (1) si tiene algún tipo de restricción artificial en N. Sin embargo, puede definir un nuevo algoritmo que tenga tiempo de ejecución [matemática] T [/ matemáticas] para todos [matemáticas] N> T. [/ matemáticas]

Entonces, por ejemplo, si el algoritmo en cuestión es encontrar el valor máximo en una matriz, es [matemática] O (N) [/ matemática] independientemente de sus límites prácticos en [matemática] N. [/ Matemática] Sin embargo, usted puede modificarlo de modo que ignore la entrada más allá del límite que le asigne. Si su límite de entrada es una matriz con 100 elementos y le da una matriz con 1000 elementos, solo encontrará el valor máximo de los primeros 100 elementos.

Este nuevo algoritmo será [math] O (1). [/ Math]

Notación O grande – Wikipedia

Si un algoritmo se ejecuta en tiempo O (N), pero N no excede una constante, ¿puedo decir que el algoritmo se ejecuta en tiempo constante?

Aquí hay un ejemplo. Quiero ordenar una matriz. Dado que el lenguaje permite a lo sumo 2 ^ 31 – 1 elementos en la matriz, ¿la clasificación de fusión (O (n log n)) y la clasificación de burbuja (O (n ^ 2)) tienen la misma complejidad de tiempo?

La respuesta es “por supuesto que no”. Si tiene el doble de elementos, espera un poco más del doble de tiempo con el tipo de fusión. Espera aproximadamente cuadruplicar el tiempo con la clasificación de burbujas.

Pero tal vez estás haciendo la pregunta equivocada. Tal vez su pregunta es “Dado que n es pequeño, ¿es posible que no me importe mucho la complejidad?” Eso es completamente posible.

Solía ​​trabajar en un lugar que tenía una habitación segura sin acceso a internet. Uno de mis compañeros de trabajo estaba haciendo ruidos “tsk, tsk” mientras miraba el código de otra persona. Le pregunté por qué, y dijo que el código estaba usando el tipo burbuja. Le pregunté qué debería usar en su lugar, y él dijo quicksort.

Le pregunté si sabía cómo escribir quicksort, y dijo que no. Le dije dónde había un libro en mi escritorio que lo tenía. Caminó a mi oficina y regresó, tomando un poco más de 5 minutos.

Señalé que el código solo ordenaba 10 elementos y solo se ejecutaba una vez al mes. Le pedí que calcule cuánto tiempo tomaría el código de clasificación si se ejecutara durante los próximos diez años. Eran menos de 5 minutos. Le dije que ya usaba demasiado tiempo para obtener el libro y que no debía cambiar el código.

Agregando a la respuesta de Bill Province.

Sea P (k) el tiempo de ejecución del algoritmo para el tamaño de entrada k. Al especificar el tiempo de ejecución del algoritmo, puede incluir el límite en el tamaño de entrada, y transmitirá la naturaleza del problema mucho mejor que decir su tiempo O (1)

Tiempo de ejecución = O (P (k)) … k

Entonces, en su caso, el tiempo de ejecución sería O (k).

He visto a mucha gente cambiar a k en lugar de N en tales casos. No es que importe, solo reduce la confusión ya que N se usa en un sentido general.

Nota: puede que haya dicho cosas triviales, pero transmite mucho más al lector del análisis algorítmico, que seguir con O (1) u O (N).

Solo puede decir que si [math] N [/ math] no depende de la entrada dada y [math] N [/ math] es lo mismo para cualquier entrada dada.

Según su pregunta, parece que [math] N [/ math] depende de la entrada, por lo tanto, en ese caso, el tiempo de ejecución no puede considerarse constante porque cambia con cada nueva entrada dada.

No, no puedes, no es así como funcionan las anotaciones O. Se podría decir que casi cualquier algoritmo O (n) se ejecuta en tiempo constante O (2147483647) en el que tendría razón. El 2147483647 es un entero máximo de 32 bits.

La notación O es más bien una comparación entre diferentes algoritmos que no dependen de su uso. Y tampoco teniendo en cuenta la velocidad de procesamiento de datos.

Mientras N sea constante, independientemente del valor pequeño o grande de N constante, diremos que el algoritmo se ejecuta en tiempo constante. es decir, la complejidad computacional del algoritmo sería O (1).

No.

Si el algoritmo es O (n), eso significa que su peor tiempo de ejecución depende del valor de entrada n. Si sabe que n no puede exceder, digamos, 10 para su caso de uso de lo que todavía se ejecutará en el tiempo O (n) para valores de n = 1–10. Decir que este algoritmo se ejecuta en O (1) sería incorrecto porque O (1) indica que “el tiempo de ejecución de este algoritmo no depende del tamaño de entrada”, que sabemos que es falso si de hecho es O (n).

Por ejemplo, si creé una versión de clasificación rápida que ordenó alfabéticamente a los Senetors de EE. UU., El peor tiempo de ejecución del algoritmo seguirá siendo O (n ^ 2), aunque siempre habrá solo 100 Senetors para ordenar. Conocer los límites superiores en el tamaño de entrada no hace que el tiempo lineal sea constante.

No. Digamos que el valor máximo de N es 100. Sería permisible (aunque no particularmente útil) decir que el programa es O (100), pero eso no es lo mismo que decir que se ejecuta en tiempo constante, lo que está diciendo que el programa se ejecuta en la misma cantidad de tiempo para N = 1 que para N = 100.

No, cada vez que te sientas confundido ve a la definición de Big O, literalmente.

Si hay una prueba definitiva de que N tiene un límite superior finito, entonces es tiempo constante.