Supongo que te refieres a la “Gran O” de un algoritmo. Este es un tema cubierto en la mayoría de las clases introductorias de CS de la universidad y el plan de estudios AP Computer Science.
Big O describe cómo cambia el tiempo de ejecución del algoritmo en relación con el tamaño del conjunto de datos en el que está trabajando, en el peor de los casos. Esto generalmente está relacionado con la cantidad de veces que los bucles en el algoritmo deben ejecutarse en relación con el conjunto de datos, pero no con cuántos pasos están involucrados en cada iteración.
Algunos ejemplos:
- Cómo escribir un programa simple usando pseudocódigos
- ¿Alguna vez ha enviado un artículo científico sobre un algoritmo que funciona tan bien como los métodos más modernos pero realmente no sabe por qué? ¿Puedes decir 'tal vez' al explicar tu método?
- Teoría de grafos: ¿en qué se diferencian los árboles de expansión construidos a partir de Prim de los árboles de expansión construidos a partir de Kruskal?
- ¿Qué es un algoritmo para el reemplazo de página (memoria virtual) LRU y FIFO?
- ¿Se puede ordenar una lista enlazada circular?
Una búsqueda lineal que itera sobre una matriz sin clasificar, buscando un valor particular, es O (n), o tiempo “lineal”, a medida que la matriz se hace más grande, el peor tiempo de búsqueda aumenta linealmente. (El tiempo que lleva inspeccionar cada elemento de la matriz, de principio a fin).
Una búsqueda binaria que busca un valor en una matriz ordenada es O (log2 n), porque la mitad de la matriz se elimina cada vez que el elemento inspeccionado no es el valor de búsqueda, porque en una búsqueda binaria se sabe del valor encontrado qué mitad de la matriz restante en la que debe estar el valor deseado (si existe). Esto significa que para una matriz de longitud N, el número máximo de iteraciones requeridas es solo log2 N, que puede ser mucho menor que N a medida que N crece.
Un bucle anidado en el que el bucle interno depende del valor del bucle externo es frecuentemente O (N ^ 2), porque el bucle interno se ejecutará hasta N veces por cada iteración del bucle externo, en el peor de los casos. N * N o N ^ 2.
Por lo tanto, inspeccione el algoritmo en cuestión, busque los bucles y determine el número de iteraciones en el peor de los casos en función del tamaño de los datos de entrada.
