¿Qué es la notación big-O? ¿Cómo se te ocurren figuras como O (n)?

Question

Duplicar posible:
Plain english explanation of Big O

Me imagino que esto es probablemente algo que se enseña en las clases, pero como un programador autodidacta, sólo he visto en raras ocasiones.

He deducido que es algo relacionado con el tiempo, y O (1) es el mejor, mientras que cosas como O (n^n) son muy malas, pero ¿alguien podría indicarme una explicación básica de qué en realidad representa, y de dónde provienen estos números?

Answer 1

Big O se refiere a la peor orden de tiempo de ejecución. Se usa para mostrar qué tan bien se escala un algoritmo en función del tamaño del conjunto de datos (n-> número de elementos).

Como solo nos preocupa el orden, los multiplicadores constantes se ignoran y los términos que aumentan menos rápidamente que el término dominante también se eliminan. Algunos ejemplos:

Una sola operación o conjunto de operaciones es O (1), ya que lleva un tiempo constante (no varía en función del tamaño del conjunto de datos).

Un bucle es O (n). Cada elemento en el conjunto de datos se coloca en bucle.

Un bucle anidado es O (n^2). Un bucle anidado anidado es O (n^3) y hacia adelante.

Cosas como la búsqueda de árbol binario son log (n), que es más difícil de mostrar, pero en cada nivel del árbol, el número posible de soluciones se reduce a la mitad, por lo que el número de niveles es log (n) (proporcionado el árbol está equilibrado).

Algo así como encontrar la suma de un conjunto de números que está más cerca de un valor dado es O (n!), Ya que la suma de cada subconjunto debe calcularse. Esto es muy malo.

Answer 2

Es una forma de expresar la complejidad del tiempo.

O(n) significa para n elementos en una lista, toma n cálculos para ordenar la lista. Lo cual no está nada mal. Cada aumento en n aumenta la complejidad del tiempo linealmente.

O(n^n) es malo, porque la cantidad de computación requerida para realizar una clasificación (o lo que sea que esté haciendo) aumentará exponencialmente a medida que aumente n.

O(1) es el mejor, ya que significa 1 cálculo para realizar una función, pensar en tablas hash, buscar un valor en una tabla hash tiene O(1) complejidad de tiempo.

Answer 3

La notación Big O aplicada a un algoritmo se refiere a cómo el tiempo de ejecución del algoritmo depende de la cantidad de datos de entrada. Por ejemplo, un algoritmo de clasificación tomará más tiempo para ordenar un conjunto de datos grande que un pequeño conjunto de datos. Si para el ejemplo del algoritmo de ordenación se grafica el tiempo de ejecución (eje vertical) frente al número de valores a ordenar (eje horizontal), para números de valores de cero a un número grande, la naturaleza de la línea o curva resultante será Depende del algoritmo de clasificación utilizado. La notación Big O es un método abreviado para describir la línea o curva.

En notación O grande, la expresión entre paréntesis es la función graficada.Si se incluye una variable (digamos n) en la expresión, esta variable se refiere al tamaño del conjunto de datos de entrada. Usted dice que O (1) es el mejor. Esto es cierto porque el gráfico f (n) = 1 no varía con n. Un algoritmo O (1) toma la misma cantidad de tiempo para completar independientemente del tamaño del conjunto de datos de entrada. Por el contrario, el tiempo de ejecución de un algoritmo de O (n^n) aumenta con el cuadrado del tamaño del conjunto de datos de entrada.

Esa es la idea básica, para una explicación detallada, consulte la página de la wikipedia titulada 'Big O Notation'.