algorithm - resueltos - Ejemplos de algoritmos que tienen complejidades O(1), O(n log n) y O(log n)
complejidad en el tiempo (9)
La complejidad de la aplicación de software no se mide y no está escrita en notación de gran O. Solo es útil para medir la complejidad del algoritmo y para comparar algoritmos en el mismo dominio. Muy probablemente, cuando decimos O (n), queremos decir que es "O (n) comparaciones " u "O (n) operaciones aritméticas". Eso significa que no puede comparar ningún par de algoritmos o aplicaciones.
¿Cuáles son algunos algoritmos que utilizamos a diario que tienen complejidades O (1), O (n log n) y O (log n)?
O (1) - Eliminar un elemento de una lista doblemente vinculada. p.ej
typedef struct _node {
struct _node *next;
struct _node *prev;
int data;
} node;
void delete(node **head, node *to_delete)
{
.
.
.
}
O (1) - la mayoría de los procedimientos de cocción son O (1), es decir, toma una cantidad de tiempo constante, incluso si hay más personas para cocinar (hasta cierto punto, porque podría quedarse sin espacio en la olla / sartenes) y necesita dividir la cocina)
O (logn) - encontrar algo en su directorio telefónico. Piensa en la búsqueda binaria.
O (n) - leyendo un libro, donde n es el número de páginas. Es la cantidad mínima de tiempo que toma leer un libro.
O (nlogn): no puedo pensar de inmediato en algo que uno pueda hacer todos los días que sea nlogn ... a menos que clasifique tarjetas haciendo fusión o clasificación rápida.
O (1): encontrar el mejor próximo movimiento en Chess (o ir para el caso). Como la cantidad de estados de juego es finita, solo es O (1) :-)
O (n log n) es famoso por el límite superior de la rapidez con la que puede ordenar un conjunto arbitrario (suponiendo un modelo informático estándar y no altamente paralelo).
Puede agregar los siguientes algoritmos a su lista:
O(1) - Determinando si un número es par o impar; Trabajando con HashMap
O(logN) - computar x ^ N,
O(N Log N) - Subsecuencia creciente más larga
Puedo ofrecerte algunos algoritmos generales ...
- O (1): Accediendo a un elemento en una matriz (es decir, int i = a [9])
- O (n log n): rápido o mergesort (en promedio)
- O (log n): búsqueda binaria
Estas serían las respuestas viscerales, ya que esto parece una especie de pregunta de deberes / entrevistas. Si está buscando algo más concreto, es un poco más difícil ya que el público en general no tendría idea de la implementación subyacente (ahorrando fuente abierta del curso) de una aplicación popular, ni el concepto en general se aplica a una "aplicación"
Si desea ejemplos de Algoritmos / Grupo de declaraciones con complejidad de tiempo como se indica en la pregunta, aquí hay una pequeña lista:
O (1) vez
1. Acceder al índice de matriz (int a = ARR [5];)
2. Insertar un nodo en la lista vinculada
3. Empujar y hacer estallar en pila
4. Inserción y eliminación de la cola
5. Averiguar el hijo primario o izquierdo / derecho de un nodo en un árbol almacenado en Array
6. Salto al elemento Siguiente / Anterior en la Lista doblemente enlazada
y puedes encontrar un millón de ejemplos más ...
A tiempo
1. Atravesando una matriz
2. Atravesando una lista enlazada
3. Búsqueda lineal
4. Eliminación de un elemento específico en una lista vinculada (no ordenada)
5. Comparando dos cadenas
6. Comprobación de Palindrome
7. Clasificación de conteo / cubeta
y aquí también puedes encontrar un millón de ejemplos más ...
En pocas palabras, todos los algoritmos de fuerza bruta, o los nobles que requieren linealidad, se basan en la complejidad del tiempo O (n)
Hora O (log n)
1. Búsqueda binaria
2. Encontrar el número más grande / más pequeño en un árbol de búsqueda binario
3. Ciertos algoritmos de división y conquista basados en la funcionalidad lineal
4. Cálculo de números de Fibonacci - Mejor método
La premisa básica aquí NO es usar los datos completos, y reducir el tamaño del problema con cada iteración
Hora O (nlogn)
1. Fusionar Ordenar
2. Heap Sort
3. Clasificación rápida
4. Ciertos algoritmos de división y conquista basados en la optimización de algoritmos O (n ^ 2)
El factor de ''log n'' se introduce al considerar Divide y Conquista. Algunos de estos algoritmos son los mejores optimizados y se usan con frecuencia.
O (n ^ 2) tiempo
1. Bubble Sort
2. Insertion Sort
3. Selección de clasificación
4. Atravesando una matriz 2D simple
Se supone que estos son los algoritmos menos eficientes si sus homólogos O (nlogn) están presentes. La aplicación general puede ser Brute Force aquí.
Espero que esto responda bien a tu pregunta. Si los usuarios tienen más ejemplos para agregar, estaré más que feliz :)
Un ejemplo simple de O(1) podría ser el return 23; - Cualquiera que sea la entrada, esto volverá en un tiempo fijo y finito.
Un ejemplo típico de O(N log N) sería ordenar una matriz de entrada con un buen algoritmo (por ejemplo, mergesort).
Un ejemplo típico si O(log N) estaría buscando un valor en una matriz de entrada ordenada por bisección.