O (1) (Complejidad constante) : en otras palabras, ¿qué toma siempre la misma cantidad de tiempo o usa la misma cantidad de espacio independientemente del tamaño de su entrada?
- Bueno, si tenemos una matriz con 50 elementos; Siempre podemos acceder a cualquiera de los 50 elementos directamente en un pequeño número de operaciones. A nivel de máquina, solo está agregando el índice a un puntero y devolviendo el valor.
O (lg n) (Complejidad logarítmica) : en otras palabras, a medida que n se vuelve muy grande, la complejidad del tiempo aumenta un poco. Para ver este tipo de rendimiento, necesitamos analizar un conjunto particular de problemas. Queremos ver el crecimiento por potencias de dos, o que el problema se reduzca por potencias de dos.
- Recorrido recursivo: los árboles binarios tienen dos hijos para cada nodo. Esto significa que la raíz tiene 1 nodo en la profundidad 0; 2 nodos en la profundidad 1; 4 nodos en la profundidad 2; 8 nodos en la profundidad 3, etc., por lo que el número de nodos aumenta en una potencia de dos a medida que avanza. Esto significa que en un árbol perfectamente equilibrado, la profundidad de un nodo hoja con 10000000 nodos totales es solo 24. (lg (2) (10000000) = 23.25). Por lo tanto, ubicar un nodo en un árbol de búsqueda binario (el hijo izquierdo tiene valores menores que el padre, el derecho tiene valores mayores que el padre) está en el orden de O (lg n) donde n es el número de nodos en el árbol.
- Iterativo: Dada una matriz 1D de enteros ordenados, realizar una búsqueda binaria arrojará un resultado en O (lg n).
O (n) (Complejidad lineal) : en otras palabras, si duplica el lado de entrada, debería ver que el programa termina en el doble de tiempo. O duplicar la entrada duplica la cantidad de memoria utilizada.
- La inmutabilidad es primordial en la mayoría de los dominios de FP, pero ¿hacen copias superficiales o profundas?
- ¿Debo aprender algoritmos si quiero ser desarrollador web / móvil?
- ¿Cómo mejorarías el algoritmo de autocorrección?
- Cómo construir un gráfico si se proporciona el recorrido DFS y el recorrido BFS
- ¿Cuál es el algoritmo de esta pregunta de Hacker-Rank?
- Un ejemplo fácil es encontrar el valor máximo de una matriz dada. Si tiene 50 elementos, puede acceder a cada elemento en O (1) tiempo, pero tiene que hacer esa operación constante n veces para verificar que el valor que encuentre sea de hecho más grande que cualquier otro elemento de la matriz. Si toma 1 segundo encontrar el máximo de 1000 elementos, debe esperar encontrar el máximo de 2000 elementos en 2 segundos.
O (n ^ 2) (Complejidad polinómica de grado 2) : en otras palabras, debe realizar n operaciones de tiempo constante para cada una de las n entradas.
- Dado un conjunto de enteros n por n, la impresión de todos ellos será O (n ^ 2). Una matriz de 5 × 5 tiene 25 valores. Una matriz de 10 × 10 tiene 100 valores. Duplicar el parámetro de entrada más que duplica la cantidad de trabajo por hacer.
