La eficiencia de un algoritmo depende de dos parámetros:
- Complejidad del tiempo
- Complejidad espacial
Complejidad del tiempo: la complejidad del tiempo se define como el número de veces que se ejecuta un conjunto de instrucciones en particular en lugar del tiempo total que lleva. Es porque el tiempo total que tomó también depende de algunos factores externos como el compilador utilizado, la velocidad del procesador, etc.
Complejidad espacial: La complejidad espacial es el espacio de memoria total requerido por el programa para su ejecución.
Ambos se calculan en función del tamaño de entrada (n).
Una cosa importante aquí es que, a pesar de estos parámetros, la eficiencia de un algoritmo también depende de la naturaleza y el tamaño de la entrada.
Tipos de complejidad temporal:
- Mejor complejidad de tiempo: defina la entrada para la cual el algoritmo toma menos tiempo o tiempo mínimo. En el mejor de los casos, calcule el límite inferior de un algoritmo. Ejemplo: en la búsqueda lineal, cuando los datos de búsqueda están presentes en la primera ubicación de datos grandes, ocurre el mejor de los casos.
- Complejidad de tiempo promedio: en el caso promedio, tome todas las entradas aleatorias y calcule el tiempo de cálculo para todas las entradas.
Y luego lo dividimos por el número total de entradas. - Complejidad de peor tiempo: defina la entrada para la cual el algoritmo tarda mucho tiempo o el tiempo máximo. En el peor de los casos, calcule el límite superior de un algoritmo. Ejemplo: En la búsqueda lineal, cuando los datos de búsqueda están presentes en la última ubicación de datos grandes, ocurre el peor de los casos.
La siguiente es una hoja de revisión rápida que puede consultar en el último minuto
| Algoritmo | Complejidad del tiempo | Complejidad espacial | ||
|---|---|---|---|---|
| Mejor | Promedio | El peor | El peor | |
| Clasificación de selección | Ω(n^2) | θ(n^2) | O(n^2) | O(1) |
| Ordenamiento de burbuja | Ω(n) | θ(n^2) | O(n^2) | O(1) |
| Tipo de inserción | Ω(n) | θ(n^2) | O(n^2) | O(1) |
| Ordenar montón | Ω(n log(n)) | θ(n log(n)) | O(n log(n)) | O(1) |
| Ordenación rápida | Ω(n log(n)) | θ(n log(n)) | O(n^2) | O(registro(n)) |
| Ordenar por fusión | Ω(n log(n)) | θ(n log(n)) | O(n log(n)) | En) |
| Clasificación de cubo | Ω(n+k) | θ(n+k) | O(n^2) | En) |
| Clasificación Radix | Ω(nk) | θ(nk) | O (nk) | O(n + k) |
| Ordenar conteo | Ω(n+k) | θ(n+k) | O(n+k) | OK) |
| Clasificación de concha | Ω(n) | θ(n log(n)) | O(n log(n)) | O(1) |
| Ordenar Tim | Ω(n) | θ(n log(n)) | O(n registro (n)) | En) |
| Clasificación de árbol | Ω(n log(n)) | θ(n log(n)) | O(n^2) | En) |
| Clasificación de cubo | Ω(n) | θ(n log(n)) | O(n log(n)) | En) |
Ver también:
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA