algorithm - online - ¿Es la complejidad de tiempo del algoritmo vacío O(0)?
complejidad de algoritmos (13)
0 = O (f) para toda la función f, ya que 0 <= | f |, entonces también es O (0).
Entonces, dado el siguiente programa:
¿La complejidad de tiempo de este programa es O (0)? En otras palabras, ¿es 0 O (0)?
Pensé que responder esto en otra pregunta arrojaría algo de luz sobre esta pregunta .
EDITAR: ¡Muchas buenas respuestas aquí! Todos estamos de acuerdo en que 0 es O (1). La pregunta es, ¿es 0 O (0) también?
Big O es notación asintótica. Para usar la O grande, necesita una función ; en otras palabras, la expresión debe ser parametrizada por n, incluso si n no se usa. No tiene sentido decir que el número 5 es O (n), es la función constante f (n) = 5 que es O (n).
Entonces, para analizar la complejidad del tiempo en términos de O grande necesitas una función de n. Su algoritmo siempre hace posiblemente 0 pasos, pero sin un parámetro variable, hablar de comportamiento asintótico no tiene sentido. Suponga que su algoritmo está parametrizado por n. Solo ahora puedes usar la notación asintótica. No tiene sentido decir que es O (n 2 ), o incluso O (1), si no especificas qué es n (o la variable oculta en O (1)).
Tan pronto como se establece en el número de pasos, es una cuestión de la definición de gran O: la función f (n) = 0 es O (0).
Dado que esta es una pregunta de bajo nivel, depende del modelo de computación. Bajo suposiciones "idealistas", es posible que no hagas nada. Pero en Python, no se puede decir def f(x): pero solo def f(x): pass . Si supone que cada instrucción, incluso el pass (NOP), lleva tiempo, entonces la complejidad es f (n) = c para alguna constante c, y a menos que c != 0 solo puede decir que f es O (1), no O (0).
Vale la pena notar que el gran O por sí mismo no tiene nada que ver con los algoritmos. Por ejemplo, puede decir sin x = x + O (x 3 ) cuando se habla de la expansión de Taylor. Además, O (1) no significa constante, significa limitado por constante.
Dada la definición formal de Big O:
Deje f (x) yg (x) ser dos funciones definidas sobre el conjunto de números reales. Entonces, escribimos:
f(x) = O(g(x)) cuando x se aproxima al infinito si existe una M real y una real x0, de modo que:
|f(x)| <= M * |g(x)| for every x > x0
Como yo lo veo, si sustituimos g (x) = 0 (para tener un programa con complejidad O (0)), debemos tener:
|f(x)| <= 0 |f(x)| <= 0 , para cada x> x0 (la restricción de existencia de un real M y x0 prácticamente se levanta aquí)
que solo puede ser verdadero cuando f (x) = 0.
Entonces, yo diría que no solo el programa vacío es O (0), sino que es el único que tiene eso. Intuitivamente, esto debería haber sido cierto ya que O (1) abarca todos los algoritmos que requieren un número constante de pasos, independientemente del tamaño de su tarea, incluyendo 0. Es esencialmente inútil hablar de O (0); ya está en O (1). Sospecho que es puramente por simplicidad de definición que usamos O(1) , donde podría ser O(c) o algo similar.
De la Wikipedia :
Una descripción de una función en términos de notación O grande generalmente solo proporciona un límite superior en la tasa de crecimiento de la función.
A partir de esta descripción, dado que el algoritmo vacío requiere 0 tiempo para ejecutarse, tiene un rendimiento de límite superior de O (0). Esto significa que también es O (1), que resulta ser un límite superior más grande.
Editar :
Más formalmente de CLR (1ed, pg 26):
Para una función dada g ( n ), denotamos O ( g ( n )) el conjunto de funciones
O ( g ( n )) = { f ( n ): existen constantes positivas c y n 0 tales que 0 ≤ f (n) ≤ cg ( n ) para todo n ≥ n 0 }
El rendimiento de tiempo asintótico del algoritmo vacío, ejecutándose en tiempo 0 independientemente de la entrada, es por lo tanto un miembro de O (0).
Editar 2 :
Todos estamos de acuerdo en que 0 es O (1). La pregunta es, ¿es 0 O (0) también?
De acuerdo con las definiciones, digo que sí.
Además, creo que hay un poco más de importancia en la pregunta de lo que indican muchas respuestas. Por sí mismo, el algoritmo vacío probablemente no tenga sentido. Sin embargo, siempre que se especifique un algoritmo no trivial, se podría pensar que el algoritmo vacío se encuentra entre los pasos consecutivos del algoritmo que se especifica, así como antes y después de los pasos del algoritmo. Es bueno saber que la "nada" no afecta el rendimiento de tiempo asintótico del algoritmo.
Editar 3 :
Adam Crume hace la siguiente claim :
Para cualquier función f ( x ), f ( x ) está en O ( f ( x )).
Prueba: que S sea un subconjunto de R y T sea un subconjunto de R * (los números reales no negativos) y sea f ( x ): S -> T y c ≥ 1. Luego 0 ≤ f ( x ) ≤ f ( x ) que conduce a 0 ≤ f ( x ) ≤ cf ( x ) para todo x∈ S. Por lo tanto f ( x ) ∈ O ( f ( x )).
Específicamente, si f ( x ) = 0 entonces f ( x ) ∈ O (0).
Debería ser O (1). El coeficiente es siempre 1.
Considerar:
Si algo crece como 5n, no dices O (5n), dices O (n) [en otras palabras, O (1n)]
Si algo crece como 7n ^ 2, no dices O (7n ^ 2), dices O (n ^ 2) [en otras palabras, O (1n ^ 2)]
Del mismo modo, deberías decir O (1), no O (alguna otra constante)
Lleva la misma cantidad de tiempo ejecutar independientemente de la entrada, por lo tanto, es O (1) por definición.
No existe tal cosa como O(0) . Incluso una máquina oracle o una hipercomputadora requieren el tiempo para una operación, es decir, solve(the_goldbach_conjecture) , ergo:
Todas las máquinas, teóricas o reales, finitas o infinitas producen algoritmos con una complejidad temporal mínima de O(1) .
Pero, de nuevo, este código aquí es O(0) :
// Hello world!
:)
No. Por convención, es O (c) siempre que no dependa del tamaño de entrada, donde c es cualquier constante positiva (generalmente se usa 1 - O (1) = O (12.37)).
O (1) significa que la complejidad del tiempo del algoritmo es siempre constante.
Digamos que tenemos este algoritmo (en C):
void doSomething(int[] n)
{
int x = n[0]; // This line is accessing an array position, so it is time consuming.
int y = n[1]; // Same here.
return x + y;
}
Estoy ignorando el hecho de que la matriz podría tener menos de 2 posiciones, solo para mantenerlo simple.
Si contamos las 2 líneas más caras, tenemos un tiempo total de 2.
2 = O (1), porque:
2 <= c * 1, si c = 2, por cada n> 1
Si tenemos este código:
public void doNothing(){}
Y lo consideramos que tiene 0 líneas expansivas, no hay diferencia en decir que tiene O (0) O (1) u O (1000), porque para cada una de estas funciones, podemos probar el mismo teorema.
Normalmente, si el algoritmo toma un número constante de pasos para completar, decimos que tiene O (1) complejidad de tiempo.
Supongo que esto es solo una convención, porque puedes usar cualquier número constante para representar la función dentro de O ().
Tengo un argumento muy simple para que el algoritmo vacío sea O (0): para cualquier función f (x), f (x) está en O (f (x)). Simplemente deje f (x) = 0, y tengamos que 0 (el tiempo de ejecución del algoritmo vacío) está en O (0).
En una nota lateral, odio que la gente escriba f (x) = O (g (x)), cuando debería ser f (x) ∈ O (g (x)).
Todas las respuestas hasta ahora abordan la pregunta como si hubiera una respuesta correcta y una respuesta incorrecta. Pero no hay. La pregunta es una cuestión de definición. Por lo general, en la teoría de la complejidad, el costo del tiempo es un número entero, aunque eso también es solo una definición. Puedes decir que el algoritmo vacío que se cierra inmediatamente toma 0 pasos de tiempo o 1 paso de tiempo. Es una pregunta abstracta porque la complejidad del tiempo es una definición abstracta. En el mundo real, ni siquiera tienes pasos de tiempo, tienes tiempo físico continuo; puede ser cierto que una CPU tiene ciclos de reloj, pero una computadora paralela podría tener fácilmente relojes asíncronos y, en cualquier caso, un ciclo de reloj es extremadamente pequeño.
Dicho esto, diría que es más razonable decir que la operación de detención lleva 1 paso de tiempo en lugar de que tome 0 pasos de tiempo. Parece más realista. Para muchas situaciones, es posiblemente muy conservador, porque la sobrecarga de la inicialización suele ser mucho mayor que la ejecución de una operación aritmética o lógica. Dar al algoritmo vacío 0 pasos de tiempo solo sería razonable para modelar, por ejemplo, una llamada de función que es eliminada por un compilador de optimización que sabe que la función no hará nada.
Varias respuestas dicen que la complejidad es O (1) porque el tiempo es una constante y el tiempo está limitado por el producto de algún coeficiente y 1. Bueno, es cierto que el tiempo es una constante y está limitado de esa manera, pero eso no quiere decir que la mejor respuesta es O (1).
Considere un algoritmo que se ejecuta en tiempo lineal. Normalmente se designa como O (n) pero juguemos al abogado del diablo. El tiempo está limitado por el producto de algún coeficiente y n ^ 2. Si consideramos que O (n ^ 2) es un conjunto, el conjunto de todos los algoritmos cuya complejidad es lo suficientemente pequeña, entonces los algoritmos lineales están en ese conjunto. Pero eso no significa que la mejor respuesta sea O (n ^ 2).
El algoritmo vacío está en O (n ^ 2) y en O (n) y en O (1) y en O (0). Yo voto por O (0).
Yo diría que es O (1) por definición, pero O (0) si quieres obtener información técnica al respecto: ya que O (k 1 g (n)) es equivalente a O (k 2 g (n)) para cualquier constante k 1 yk 2 , se deduce que O (1 * 1) es equivalente a O (0 * 1), y por lo tanto O (0) es equivalente a O (1).
Sin embargo , el algoritmo vacío no es como, por ejemplo, la función de identidad, cuya definición es algo así como "devuelve tu entrada". El algoritmo vacío es más como un enunciado vacío, o lo que sea que ocurra entre dos enunciados. Su definición es "no hacer absolutamente nada con su entrada", presumiblemente sin siquiera la sobrecarga implícita de simplemente tener entrada.
En consecuencia, la complejidad del algoritmo vacío es única en el sentido de que O (0) tiene una complejidad de cero veces cualquiera que sea la función que le apetezca, o simplemente cero. De esto se deduce que dado que todo el negocio es tan loco, y dado que O (0) ya no significa algo útil, y dado que es un poco ridículo incluso discutir tales cosas, un caso especial razonable para O (0) es algo como esto:
La complejidad del algoritmo vacío es O (0) en tiempo y espacio. Un algoritmo con complejidad de tiempo O (0) es equivalente al algoritmo vacío.
Ahí vas.