¿Cuáles son las características de un algoritmo de complejidad de tiempo ?

A veces es fácil identificar la complejidad temporal de un algoritmo si lo examino cuidadosamente. Los algoritmos con dos bucles anidados de son obviamente . Los algoritmos que exploran todas las combinaciones posibles de grupos de dos valores son obviamenteN 2 N 2 $N$$N^2$$N$$2^N$ .

Sin embargo, no sé cómo "detectar" un algoritmo con complejidad . Una implementación recursiva de mergesort, por ejemplo, es una. ¿Cuáles son las características comunes de mergesort u otroΘ ( N log N $\Theta(N \log N)$$\Theta(N \log N)$ algoritmos que me darían una pista si estuviera analizando uno?

Estoy seguro de que hay más de una forma en que un algoritmo puede ser de complejidad , por lo que se aprecian todas y cada una de las respuestas. Por cierto, estoy buscando características generales y consejos, no pruebas rigurosas.$\Theta(N \log N)$

Su arquetípico es un algoritmo de divide y vencerás , que divide (y recombina) el trabajo en tiempo lineal y se repite sobre las piezas. La ordenación por fusión funciona de esa manera: pasa tiempo dividiendo la entrada en dos partes más o menos iguales, ordena recursivamente cada pieza y gastaO ( n ) Θ ( n $\Theta(n \log n)$$O(n)$$\Theta(n)$ combinando las dos mitades ordenadas.

Intuitivamente, continuando con la idea de dividir y conquistar, cada etapa de división toma tiempo lineal en total, porque el aumento en el número de piezas para dividir coincide exactamente con la disminución en el tamaño de las piezas, ya que el tiempo que toma la división es lineal. El tiempo total de ejecución es el producto del costo total de una etapa de división multiplicado por el número de etapas de división. Dado que el tamaño de las piezas se reduce a la mitad en cada momento, hay etapas de división , por lo que el tiempo total de ejecución es . (Hasta una constante multiplicativa, la base del logaritmo es irrelevante).n ⋅ log ( n $\log_2(n)$$n \cdot \log(n)$

Poniéndolo en ecuaciones (), una forma de estimar el tiempo de ejecución de dicho algoritmo es expresarlo recursivamente: T ( n ) = 2 T ( n / 2 ) + Θ ( n ) . Está claro que este algoritmo toma más que tiempo lineal, y podemos ver cuánto más dividiendo por n : $T(n)$$T(n) = 2 T(n/2) + \Theta(n)$$n$ Cuandon seduplica,T(n)/naumenta en una cantidad constante:T(n)/naumenta logarítmicamente, o en otras palabras,T(n)=Θ(nlogn).

Esta es una instancia de un patrón más general: el teorema maestro . Para cualquier algoritmo recursivo que divide su entrada de tamaño en una piezas de tamaño n / b y toma un tiempo f ( n ) para realizar la división y recombinación, el satisface tiempo de funcionamiento T ( n ) = a ⋅ T ( n / b ) + f ( n ) . Esto lleva a una forma cerrada que depende de los valores de a y b y la forma de$n$$a$$n/b$$f(n)$$T(n) = a \cdot T(n/b) + f(n)$$a$$b$ . Si un = b y f ( n ) = Θ ( n ) , los estados teorema maestro que T ( n ) = Θ ( n log n ) .$f$$a = b$$f(n) = \Theta(n)$$T(n) = \Theta(n \log n)$

Otras dos categorías de algoritmos que toman tiempo :$\Theta(n \log n)$

Algoritmos en los que cada elemento se procesa por turno, y se necesita un tiempo logarítmico para procesar cada elemento (por ejemplo, HeapSort o muchos de los algoritmos de geometría computacional de barrido plano).

Algoritmos en los que el tiempo de ejecución está dominado por un paso de preprocesamiento de clasificación. (Por ejemplo, en el algoritmo de Kruskal para un árbol de expansión mínimo, podemos clasificar los bordes por peso como primer paso).

Otra categoría: Algoritmos en los que la salida tiene un tamaño y, por lo tanto, el tiempo de ejecución Θ ( n log n ) es lineal en el tamaño de salida .$\Theta(n \log n)$$\Theta(n \log n)$

Aunque los detalles de tales algoritmos a menudo usan técnicas de divide y vencerás, no necesariamente tienen que hacerlo. El tiempo de ejecución proviene fundamentalmente de la pregunta que se hace, por lo que creo que vale la pena mencionarlo por separado.

Esto surge en estructuras de datos que se basan en un árbol de búsqueda binario aumentado, donde cada nodo almacena una estructura de datos de tamaño lineal para buscar sobre las hojas en el subárbol de ese nodo. Tales estructuras de datos surgen a menudo en la búsqueda de rango geométrico, y a menudo se basan en un esquema de descomposición . Ver la encuesta de Agarwal .

Para un ejemplo concreto, considere el árbol de rango , construido para responder consultas de rango ortogonales bidimensionales. Aunque el espacio se redujo más tarde utilizando algunas técnicas de compresión para empaquetar múltiples objetos en una sola palabra, la versión de libro de texto (y la más intuitiva) de la estructura de datos requiere espacio (cada hoja se almacena en una estructura auxiliar en cada nodo en la ruta de la hoja a la raíz, o en O ( log n ) lugares), y el algoritmo de construcción lleva un tiempo lineal en el requisito de espacio .$O(n \log n)$$O(\log n)$

Una complejidad de surge de los algoritmos de división y conquista que dividen su entrada en k piezas de aproximadamente el mismo tamaño en el tiempo O ( n ) , operan en estas piezas de forma recursiva y luego las combinan en el tiempo O ( n ) . Si solo opera en algunas de las piezas, el tiempo de ejecución se reduce a O ( n ) .$O(n\log n)$$k$$O(n)$$O(n)$$O(n)$

Esos son típicamente algoritmos de la variedad "divide y vencerás", donde el costo de dividir y combinar las soluciones no es "demasiado grande". Eche un vistazo a estas preguntas frecuentes para ver qué tipos de recurrencias dan lugar a este comportamiento.

Por lo general, los algoritmos de dividir y conquistar producirán complejidad O (N log N).

$O(n \log n)$

for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

$O(n^2)$

No puedo dar un ejemplo concreto de un algoritmo que usa este bucle, pero aparece a menudo al codificar algoritmos personalizados.