Saltar al contenido

¿La complejidad temporal del algoritmo vacío es O(0)?

Bienvenido a nuestra comunidad, ahora vas a encontrar la solucíon a lo que andabas buscando.

Solución:

De 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 gramo(norte), denotamos O(gramo(norte)) el conjunto de funciones

O(gramo(norte)) = F(norte): existen constantes positivas C y norte0 tal que 0 ≤ f(n) ≤ c.g.(norte) para todos nortenorte0

El rendimiento de tiempo asintótico del algoritmo vacío, que se ejecuta 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, ¿también es 0 O(0)?

Basado en las definiciones, digo que sí.

Además, creo que la pregunta tiene un poco más de importancia 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, podría pensarse que el algoritmo vacío se encuentra entre 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 del tiempo asintótico del algoritmo.

Editar 3:

Adam Crume hace la siguiente afirmación:

Para cualquier función F(X), F(X) está en O(F(X)).

prueba: dejar S ser un subconjunto de R y T ser un subconjunto de R* (los números reales no negativos) y sea F(X):S ->T y C ≥ 1. Entonces 0 ≤ F(X) ≤ F(X) lo 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).

Se necesita la misma cantidad de tiempo para ejecutarse independientemente de la entrada, por lo tanto, es O (1) por definición.

Varias respuestas dicen que la complejidad es O(1) porque el tiempo es una constante y el tiempo está acotado por el producto de algún coeficiente y 1. Bueno, es true que el tiempo es una constante y está acotado de esa manera, pero eso no significa que la mejor respuesta sea O(1).

Considere un algoritmo que se ejecuta en tiempo lineal. Normalmente se designa como O(n) pero hagamos de abogado del diablo. El tiempo está acotado 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). Voto por O(0).

Te mostramos comentarios y valoraciones

Recuerda algo, que tienes la capacidad de añadir una estimación objetiva si te ayudó.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *