Puede aprender sobre el análisis de algoritmos al comprender la complejidad computacional y cómo se mide y representa.
Hay 7 funciones de análisis (en orden de velocidad). Imagine un gráfico de tiempo relevante para la función:
- Función constante (la mejor) – f (n) = c – La estructura de datos se ejecuta en tiempos proporcionales a la función constante. Un programa se completará en la misma cantidad de tiempo, independientemente de la cantidad de entradas
- ¿Cuál es el código / algo para la multiplicación de matriz dispersa?
- ¿Qué idioma es mejor para los algoritmos de búsqueda: Java o Python? ¿Por qué?
- ¿Se utilizan las señales sociales en los algoritmos de clasificación de motores de búsqueda?
- Cómo ordenar la matriz de una estructura utilizando solo uno de sus miembros de datos en c ++ (STL)
- ¿Podemos usar una cola en quicksort en C?
- Función logarítmica (Kicks ass) – f (n) = logb (n) – (b-base, b ^ x = n)
- Función lineal (tolerable) – f (n) = n – El tiempo aumenta sustancialmente con el número de elementos. Un programa se completará en una cantidad de tiempo proporcional al número de entradas
- Función n-Log-n – f (n) = nlog (n)
- Función cuadrática – f (n) = n ^ 2 – Es menos práctico si un algoritmo se ejecuta en tiempo proporcional a una función cuadrática o más allá de este punto.
- Función cúbica – f (n) = n ^ 3
- Función exponencial – f (n) = b ^ n
Analizando Algoritmos
- Una estructura de datos organiza y proporciona una forma de acceder a los datos.
- Los algoritmos son procedimientos realizados paso a paso para resolver un problema en un tiempo finito.
- Estos , junto con las entradas y salidas impactan el tiempo de ejecución.
- Los algoritmos transforman los objetos de entrada en objetos de salida.
- Los tiempos de ejecución del algoritmo crecen con el tamaño de entrada.
- El tiempo promedio del caso es difícil de determinar porque hay demasiados tipos diferentes de entornos e insumos para considerar.
- El peor tiempo de ejecución es más fácil de analizar y es crucial para los juegos, la robótica y las aplicaciones financieras.
Podemos implementar el algoritmo para medirlo .
- Escribe un programa usando el algoritmo.
- Ejecútelo variando el tamaño de entrada y la composición.
- Mida el tiempo de ejecución real utilizando un método como System.currentTimeMillis ().
- Trazar resultados.
Limitaciones al enfoque.
- Consumir mucho tiempo : tendríamos que implementar completamente el algoritmo para estudiar su tiempo de ejecución.
- Difícil de comparar : para comparar algoritmos en tiempo de ejecución, necesitaríamos que los experimentos se realicen en los mismos entornos de hardware y software.
- No se prueban todos los datos / hay muchos datos para probar: se utilizan conjuntos de datos limitados y los que no se prueban pueden ser vitales.
Alternativa al análisis del tiempo de ejecución
- Usar una descripción de alto nivel ( pseudocódigo ) del algoritmo en lugar de implementarlo.
- Nos permite evaluar la velocidad de los algoritmos independientemente del hardware.
Operaciones primitivas
- Cálculos básicos que realiza un algoritmo que es fácilmente identificable en el código Psuedo.
- Esto es independiente de los lenguajes de programación. La definición exacta del algoritmo no es importante.
- Contamos las operaciones primitivas en un algoritmo para estimar su tiempo de ejecución.
Ejemplos de operaciones primitivas
- Evaluar una expresión – [== | ! = | | =]
- Asignación de un valor a una variable – [int i = 0; El | k ++ | – -k | Coche myCar = Audi]
- Indexación en una matriz – [matriz [2]]
- Llamando a un método – [myCar.drive ()]
- Volviendo de un método – [add (int a, int b) {return a + b; }]
- Los bucles For-, For-Each, While, Do-While, entre otros (iteradores) agregan posteriormente más complejidad computacional, ya que son repeticiones de las operaciones que ocurren dentro de ellos.
Luego determinamos si la función f (n) es Big-Oh de g (n) o el orden de g (n), estimamos el tiempo de ejecución delimitando las funciones y estimamos sus tasas de crecimiento utilizando ciertos factores determinantes que excluir.
‘Big-O ofrece una ecuación para describir cómo cambia el tiempo de un procedimiento en relación con su entrada. Describe la tendencia . No define exactamente cuánto tiempo lleva, ya que un procedimiento con un gran tiempo de O mayor que otro procedimiento podría ser más rápido en entradas específicas ”. de: Respuesta de Gayle Laakmann McDowell a ¿Cuál es la mejor manera de explicar la notación big-O en términos simples?
En el futuro, puedo agregar una explicación decente de la notación Big-Oh y el análisis de algoritmo asintótico si es necesario.
He utilizado el libro de texto Data Structures & Algorithms 5E de M.Goodrich y R.Tamassia para el análisis de algoritmos. Hago referencias al capítulo 4 – Fundamentos matemáticos en mi respuesta.
Aquí hay un proyecto mío en GitHub que demuestra la operación de conteo primitivo y muestra la notación Big-Oh, está escrito en Java: darzo27 / PrimitiveCounter
