1. Comprender la complejidad del tiempo y la complejidad del espacio:
* Complejidad del tiempo: Mide la cantidad de tiempo que se necesita un algoritmo para completar en función del tamaño de entrada (a menudo denotado como 'n'). Estamos interesados en * cómo * crece el tiempo de ejecución, no en el momento exacto en segundos.
* Complejidad espacial: Mide la cantidad de memoria (o espacio) que un algoritmo requiere en función del tamaño de entrada 'n'. Esto incluye el espacio para los datos de entrada y cualquier estructura de datos auxiliares utilizadas por el algoritmo.
2. Identificación de operaciones clave:
* Operaciones básicas: Identifique las operaciones que contribuyen significativamente al tiempo de ejecución. Estos podrían incluir:
* Operaciones aritméticas (+, -, \*, /, %)
* Comparaciones (<,>, ==,! =)
* Asignaciones (=)
* Accesos de matriz (arr [i])
* Asignaciones de memoria y traficaciones (dependiendo del idioma)
* Centrarse en las operaciones dominantes: Algunas operaciones se ejecutarán con mucha más frecuencia que otras. Concéntrese en estas operaciones * dominantes *, ya que tendrán el mayor impacto en el tiempo de ejecución general. Por ejemplo, en un algoritmo de clasificación, las comparaciones y los swaps son dominantes.
3. Analice la estructura del algoritmo (tutorial de código):
* declaraciones secuenciales: Las declaraciones ejecutadas en secuencia aportan una cantidad constante de tiempo o espacio.
* bucles: La complejidad del tiempo de un bucle depende de cuántas veces se itera:
* bucle simple (lineal): `Para i en el rango (n):... 'ejecuta' n 'veces, por lo que la complejidad es o (n).
* bucles anidados (cuadráticos, cúbicos, etc.): `Para i en el rango (n):para j en el rango (n):...` ejecuta 'n * n' veces, por lo que la complejidad es o (n^2).
* bucle con comportamiento logarítmico: `Mientras que n> 1:n =n // 2` ejecuta log2 (n) veces, por lo que la complejidad es o (log n).
* bucle con dependencia de la lógica interna: Analice el cuerpo del bucle para determinar su complejidad y multiplíquelo por el número de iteraciones.
* declaraciones condicionales (if/else):
* Analice los bloqueos `if` y` Else`. La complejidad general es el * máximo * de las complejidades de los bloques `if` y` else`.
* Para estructuras `if/else` profundamente anidadas, rastree cuidadosamente las posibles rutas de ejecución.
* Recurre:
* Identifique los casos base: Estos terminan la recursión.
* Identificar el paso recursivo: Cómo el problema se divide en subproblemas más pequeños.
* Escribe una relación de recurrencia: Esto describe matemáticamente la complejidad del tiempo de la función recursiva. Por ejemplo:`t (n) =t (n/2) + o (1)` (búsqueda binaria)
* Resuelve la relación de recurrencia: Use métodos como el teorema maestro, la sustitución o el árbol de recursión para encontrar la complejidad del tiempo asintótico.
* Llamadas de función: Considere la complejidad del tiempo de la función llamada. Si una función `A` las llamadas funcionan` B`, la complejidad del tiempo de `A` incluirá la complejidad del tiempo de 'B'.
4. Expresar complejidad en la notación asintótica (Big O, Big Omega, Big Theta):
* Big O Notación (O): Representa el * límite superior * de la tasa de crecimiento del algoritmo. Describe el escenario * peor de los casos *. "La complejidad del tiempo del algoritmo es O (n^2)" significa que el tiempo de ejecución del algoritmo no crecerá * más rápido * que n^2 a medida que aumenta 'n'.
* Big Omega Notation (ω): Representa el * inferior límite * de la tasa de crecimiento del algoritmo. Describe el escenario * Best-Case *. "La complejidad del tiempo del algoritmo es Ω (n)" significa que el tiempo de ejecución del algoritmo no crecerá * más lento * que 'n' como 'n' aumenta.
* Big theta notación (θ): Representa el * límite apretado * de la tasa de crecimiento del algoritmo. Describe el escenario de caso promedio y cuando el tiempo de ejecución del algoritmo crece a la misma velocidad que la función. "La complejidad del tiempo del algoritmo es θ (n log n)" significa que el tiempo de ejecución del algoritmo crecerá a la misma velocidad que n log n.
Complejidades de tiempo comunes (peor de los casos, Big O):
* o (1):tiempo constante: El tiempo de ejecución es independiente del tamaño de entrada. Ejemplo:acceder a un elemento en una matriz por su índice.
* o (log n):tiempo logarítmico: El tiempo de ejecución aumenta logarítmicamente con el tamaño de entrada. Ejemplo:búsqueda binaria en una matriz ordenada.
* o (n):tiempo lineal: El tiempo de ejecución aumenta linealmente con el tamaño de entrada. Ejemplo:Buscando un elemento en una matriz no organizada.
* o (n log n):tiempo linealithmic: Común en algoritmos de clasificación eficientes. Ejemplo:Fusion Sort, Quicksort (caso promedio).
* o (n^2):tiempo cuadrático: El tiempo de ejecución aumenta cuadráticamente con el tamaño de entrada. Ejemplo:clasificación de burbujas, clasificación de inserción.
* o (n^3):tiempo cúbico: Ejemplo:multiplicación de matriz.
* o (2^n):tiempo exponencial: El tiempo de ejecución se duplica con cada adición al tamaño de entrada. A menudo indica un enfoque de fuerza bruta. Ejemplo:Probar todos los subconjuntos posibles de un conjunto.
* o (n!):tiempo factorial: El tiempo de ejecución crece extremadamente rápidamente. Ejemplo:encontrar todas las permutaciones de un conjunto.
5. Ignorar factores constantes y términos de orden inferior:
Al usar notación asintótica, estamos principalmente interesados en el término * dominante * que determina la tasa de crecimiento. Los factores constantes y los términos de orden inferior se vuelven insignificantes a medida que 'n' se vuelve muy grande.
* `3n^2 + 5n + 10` se simplifica a` o (n^2) `
* `100 log n + n` se simplifica a` o (n) `(N crece más rápido que log n)
* `2^n + n^5` se simplifica a` o (2^n) `
6. Analizar la complejidad del espacio:
Similar a la complejidad del tiempo, analice el espacio utilizado por el algoritmo. Considerar:
* Espacio de entrada: El espacio requerido para almacenar los datos de entrada.
* Espacio auxiliar: El espacio adicional utilizado por el algoritmo, más allá del espacio de entrada, para variables, estructuras de datos y pila de llamadas de recursión.
Ejemplos:
* Búsqueda lineal:
`` `Python
def lineal_search (arr, objetivo):
para i en el rango (len (arr)):
Si arr [i] ==Target:
regreso
retorno -1
`` `` ``
* Complejidad del tiempo: O (n) (lineal, peor de los casos:el objetivo no está en la matriz o es el último elemento)
* Complejidad espacial: O (1) (constante, porque usa solo unas pocas variables adicionales)
* búsqueda binaria:
`` `Python
def binary_search (arr, objetivo):
bajo =0
alto =len (arr) - 1
Mientras que bajo <=alto:
Mid =(bajo + alto) // 2
Si arr [Mid] ==Target:
regresar a medio
Elif arr [Mid]
demás:
Alto =Mid - 1
retorno -1
`` `` ``
* Complejidad del tiempo: O (log n) (logarítmico)
* Complejidad espacial: O (1) (versión constante, iterativa)
* búsqueda binaria recursiva:
`` `Python
def binary_search_recursive (arr, objetivo, bajo, alto):
Si bajo> alto:
retorno -1
Mid =(bajo + alto) // 2
Si arr [Mid] ==Target:
regresar a medio
Elif arr [Mid]
demás:
return binary_search_recursive (arr, objetivo, bajo, mediano - 1)
`` `` ``
* Complejidad del tiempo: O (log n)
* Complejidad espacial: O (log n) debido a la profundidad de la recursión. Cada llamada recursiva agrega un nuevo cuadro a la pila de llamadas.
En resumen:
1. Defina lo que quieres medir: Complejidad del tiempo, complejidad del espacio o ambos.
2. Identificar las operaciones clave contribuyendo al uso de recursos.
3. Analice la estructura del algoritmo (bucles, condicionales, recursión).
4. Expresa la complejidad Usando Big O, Big Omega o Big Theta Notation.
5. Ignorar factores constantes y términos de orden inferior.
Siguiendo estos pasos, puede analizar de manera efectiva la eficiencia de los algoritmos y elegir el algoritmo más adecuado para sus necesidades específicas. Recuerde que el mejor algoritmo depende del problema específico, el tamaño de los datos de entrada y los recursos disponibles.