¿Cómo especifica f(n) <cg(n) el tiempo?

Question

Estaba leyendo este tutorial sobre la complejidad del tiempo, y estoy un poco desconcertado por su explicación de los grandes $O$ notación.Escribe:

$O(g(n)) = $ { $f(n)$ :existen constantes positivas $c$ y $n_0$ tal que $0 \leq f(n) \leq c*g(n)$ para todos $n > n_0$.

La forma en que lo entiendo, $c*g(n)$ denota $c$ multiplicado por $g(n)$.Si este es el caso, entonces ¿cómo especifica la expresión anterior el tiempo, y no sólo eso? $c*g(n)$ es mayor que $f(n)$?¿O me equivoco y se trata de una notación que no entiendo?Mi comprensión de la complejidad del tiempo es muy rudimentaria, así que perdónenme si esto es sólo un error estúpido de mi parte.

Answer 1

¿Cómo especifica f(n) <cg(n) el tiempo?

No es así.La notación de Bachmann-Landau es simplemente una forma práctica de comparar la tasa de crecimiento de funciones.No dice nada sobre ¿Qué significan esas funciones?, y podemos estar bastante seguros de que Bachmann no estaba pensando en las computadoras cuando se le ocurrió en 1894.

Qué sentido usted asigna a esas funciones depende de usted.Por ejemplo, cuando analizamos algoritmos de clasificación basados ​​en comparaciones, normalmente tomamos $n$ ser el número de elementos de la colección y $f(n)$ ser el número de comparaciones, o el número de intercambios, o el número de comparaciones e intercambios.

Tenga en cuenta también que todo esto es siempre relativo a un modelo de máquina o un modelo de costos.

Como ejemplo muy simple, si le preguntara cuál es la complejidad del paso algorítmico en el peor de los casos para copiar una lista, diría $O(n)$.Pero en realidad, el respuesta correcta sería "No puedo decírtelo porque no has especificado el modelo de máquina".Porque, por ejemplo, en una máquina de Turing, copiar una lista es $O(n^2)$, porque para cada elemento que se copia, el encabezado de la MT tiene que conducir más y más para llegar al final de la lista y escribir el siguiente elemento.

Answer 2

Diciendo que el tiempo de ejecución de un algoritmo está en $ o (g (n)) $ da, como usted señaló, solo un límite superior. Además, el límite superior se administra con las constantes $ C $ y $ n_0 $ desconocido. Así que sí, es una información bastante débil sobre el tiempo de ejecución.

El constante no especificado $ C $ puede contener la información sobre el costo real de las operaciones básicas del algoritmo, que puede ser desconocido y / o variable entre las carreras, Pero aún se sabe que cuesta una cantidad de tiempo que está limitada. El constante no especificado $ n_0 $ refleja que el límite dado se refiere a tamaños grandes de la entrada (o cualquier parámetro $ n $ < / span> está representando).

Otros símbolos se utilizan para dar otros tipos o Información más precisa sobre el tiempo de ejecución.