Dos indicadores importantes para evaluar algoritmos de estructura de datos son
Dos indicadores importantes para evaluar algoritmos de estructura de datos son la complejidad del espacio y la complejidad del tiempo.
La complejidad del espacio es una medida de la cantidad de espacio de almacenamiento ocupado temporalmente por el algoritmo durante la operación y puede escribirse como S(n)=O(f(n)). Por ejemplo, la complejidad temporal de la ordenación por inserción directa es O (n ^ 2) y la complejidad espacial es O (1). La complejidad espacial de un algoritmo recursivo general es O(n) porque la información de retorno se almacena para cada recursión. La solidez de un algoritmo se mide en términos de su tiempo de ejecución y el espacio de almacenamiento que ocupa.
En informática, la complejidad del tiempo también se denomina complejidad del tiempo. La complejidad del tiempo de un algoritmo es una función que describe cualitativamente el tiempo de ejecución del algoritmo. Es una función que representa la longitud de la cadena de valor de entrada del algoritmo. La complejidad del tiempo generalmente se expresa en O grande, excluyendo los términos de orden inferior y los primeros coeficientes de la función. Cuando se usa de esta manera, se puede decir que la complejidad del tiempo es asintótica, es decir, lo que sucede cuando el tamaño de los valores de entrada llega al infinito.
Tiempo logarítmico:
Si un algoritmo tiene T(n) = O(logn), entonces tiene tiempo logarítmico. Dado que las computadoras utilizan un sistema de notación binaria, los logaritmos suelen ser de base 2 (es decir, log2n, a veces también escrito como lgn). Sin embargo, según la fórmula de sustitución de bases logarítmicas, logan y logbn difieren sólo en un factor constante y, en notación O grande, este factor se elimina. Por lo tanto, O(logn) es la notación estándar para algoritmos de tiempo logarítmico, independientemente de la base del logaritmo.
Los algoritmos comunes con tiempo logarítmico son las operaciones de correlación de árboles binarios y la búsqueda por partes. Los algoritmos con tiempo logarítmico son muy eficientes porque requieren menos tiempo de cálculo adicional para cada entrada adicional. Cortar recursivamente a la mitad una cadena y generarla es un ejemplo simple de este tipo de función. Se necesita tiempo O(logn) porque dividimos la cadena a la mitad antes de cada salida. Esto significa que si queremos aumentar la cantidad de producción, debemos duplicar la longitud de la cadena.