Determinar las complejidades de los códigos dados
algorithm recursion (6)
En general , no hay forma de determinar la complejidad de una función dada
¡Advertencia! ¡Pared de texto entrante!
1. Hay algoritmos muy simples que nadie sabe si incluso se detienen o no.
No existe un algoritmo que pueda decidir si un programa determinado se detiene o no, si se le da una determinada entrada. Calcular la complejidad computacional es un problema aún más difícil, ya que no solo necesitamos demostrar que el algoritmo se detiene, sino que debemos demostrar cuán rápido lo hace.
//The Collatz conjecture states that the sequence generated by the following
// algorithm always reaches 1, for any initial positive integer. It has been
// an open problem for 70+ years now.
function col(n){
if (n == 1){
return 0;
}else if (n % 2 == 0){ //even
return 1 + col(n/2);
}else{ //odd
return 1 + col(3*n + 1);
}
}
2. Algunos algoritmos tienen complejidades raras y extrañas
Un "esquema de determinación de complejidad" general sería demasiado complicado debido a estos tipos
//The Ackermann function. One of the first examples of a non-primitive-recursive algorithm.
function ack(m, n){
if(m == 0){
return n + 1;
}else if( n == 0 ){
return ack(m-1, 1);
}else{
return ack(m-1, ack(m, n-1));
}
}
function f(n){ return ack(n, n); }
//f(1) = 3
//f(2) = 7
//f(3) = 61
//f(4) takes longer then your wildest dreams to terminate.
3. Algunas funciones son muy simples pero confundirán muchos tipos de intentos de análisis estático
//Mc''Carthy''s 91 function. Try guessing what it does without
// running it or reading the Wikipedia page ;)
function f91(n){
if(n > 100){
return n - 10;
}else{
return f91(f91(n + 11));
}
}
Dicho esto, todavía necesitamos una forma de encontrar la complejidad de las cosas, ¿verdad? Para los bucles son un patrón simple y común. Toma tu ejemplo inicial:
for(i=0; i<N; i++){
for(j=0; j<i; j++){
print something
}
}
Como cada print something es O (1), la complejidad de tiempo del algoritmo se determinará por la cantidad de veces que ejecutemos esa línea. Bueno, como mencionó su TA, hacemos esto mirando las combinaciones en este caso. El ciclo interno funcionará (N + (N-1) + ... + 1) veces, para un total de (N + 1) * N / 2.
Como ignoramos las constantes obtenemos O (N 2 ).
Ahora, para los casos más difíciles, podemos obtener más matemáticos. Intente crear una función cuyo valor represente cuánto tiempo tarda el algoritmo en ejecutarse, dado el tamaño N de la entrada. A menudo podemos construir una versión recursiva de esta función directamente desde el algoritmo mismo y calcular la complejidad se convierte en el problema de poner límites a esa función. Llamamos a esta función una recurrencia
Por ejemplo:
function fib_like(n){
if(n <= 1){
return 17;
}else{
return 42 + fib_like(n-1) + fib_like(n-2);
}
}
es fácil ver que el tiempo de ejecución, en términos de N, estará dado por
T(N) = 1 if (N <= 1)
T(N) = T(N-1) + T(N-2) otherwise
Bueno, T (N) es solo la buena función de Fibonacci. Podemos usar la inducción para ponerle límites a eso.
Por ejemplo, permite probar, por inducción, que T (N) <= 2 ^ n para todo N (es decir, T (N) es O (2 ^ n))
- caso base: n = 0 o n = 1
T(0) = 1 <= 1 = 2^0
T(1) = 1 <= 2 = 2^1
- caso inductivo (n> 1):
T(N) = T(n-1) + T(n-2)
aplying the inductive hypothesis in T(n-1) and T(n-2)...
T(N) <= 2^(n-1) + 2^(n-2)
so..
T(N) <= 2^(n-1) + 2^(n-1)
<= 2^n
(podemos intentar hacer algo similar para probar el límite inferior también)
En la mayoría de los casos, tener una buena estimación sobre el tiempo de ejecución final de la función le permitirá resolver fácilmente los problemas de recurrencia con una prueba de inducción. Por supuesto, esto requiere que puedas adivinar primero, solo mucha práctica te puede ayudar aquí.
Y como nota final, me gustaría señalar el teorema del Maestro , la única regla para problemas de recurrencia más difíciles que ahora puedo pensar que se usa comúnmente. Úselo cuando tenga que lidiar con un algoritmo difícil de dividir y conquistar.
Además, en su ejemplo de "si el caso", lo resolvería haciendo trampa y dividiéndolo en dos bucles separados que donan; Tengo un si dentro.
for (int i = 0; i < n; i++) {
if (i % 2 ==0) {
for (int j = i; j < n; j++) { ... }
} else {
for (int j = 0; j < i; j++) { ... }
}
}
Tiene el mismo tiempo de ejecución que
for (int i = 0; i < n; i += 2) {
for (int j = i; j < n; j++) { ... }
}
for (int i = 1; i < n; i+=2) {
for (int j = 0; j < i; j++) { ... }
}
Y cada una de las dos partes se puede ver fácilmente como O (N ^ 2) para un total que también es O (N ^ 2).
Tenga en cuenta que utilicé un buen truco truco para deshacerme del "si" aquí. No hay una regla general para hacerlo, como se muestra en el ejemplo del algoritmo Collatz
Dado un snipplet de código, ¿cómo determinarás las complejidades en general? Me encuentro muy confundido con las preguntas de Big O. Por ejemplo, una pregunta muy simple:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
}
}
El TA explicó esto con algo así como combinaciones. De esta manera, n elige 2 = (n (n-1)) / 2 = n ^ 2 + 0.5, luego elimina la constante para que se convierta en n ^ 2. Puedo poner valores de prueba int y probar, pero ¿cómo entra esta combinación?
¿Qué pasa si hay una declaración if? ¿Cómo se determina la complejidad?
for (int i = 0; i < n; i++) {
if (i % 2 ==0) {
for (int j = i; j < n; j++) { ... }
} else {
for (int j = 0; j < i; j++) { ... }
}
}
Entonces, ¿qué pasa con la recursión ...
int fib(int a, int b, int n) {
if (n == 3) {
return a + b;
} else {
return fib(b, a+b, n-1);
}
}
Aunque esto es una generalización excesiva, me gusta pensar en Big-O en términos de listas, donde la longitud de la lista es de N elementos.
Por lo tanto, si tiene un bucle for que itera sobre todo en la lista, es O (N). En su código, tiene una línea que (aisladamente por sí sola) es 0 (N).
for (int i = 0; i < n; i++) {
Si tiene un bucle for anidado dentro de otro bucle for, y realiza una operación en cada elemento de la lista que requiere que observe cada elemento de la lista, entonces está realizando una operación N veces para cada uno de los N elementos, por lo tanto O (N ^ 2). En su ejemplo anterior, de hecho, tiene otro bucle for anidado dentro de su bucle for. De modo que puede pensar en ello como si cada ciclo for es 0 (N), y luego porque están anidados, multiplíquelos por un valor total de 0 (N ^ 2).
Por el contrario, si solo está haciendo una operación rápida en un solo elemento, entonces sería O (1). No hay una ''lista de longitud n'' para repasar, solo una operación única de una vez. Para poner esto en contexto, en su ejemplo anterior, la operación:
if (i % 2 ==0)
es 0 (1). Lo que es importante no es el ''si'', sino el hecho de que verificar si un solo elemento es igual a otro elemento es una operación rápida en un solo artículo. Al igual que antes, la instrucción if está anidada dentro de su ciclo for for externo. Sin embargo, como es 0 (1), está multiplicando todo por ''1'', por lo que no hay efecto ''notable'' en el cálculo final del tiempo de ejecución de toda la función.
Para los registros y para tratar situaciones más complejas (como este negocio de contar hasta j o yo, y no solo de nuevo), te indicaría una explicación más elegante here .
Big-O es solo una aproximación, no dice cuánto tarda en ejecutarse un algoritmo, solo dice algo acerca de cuánto tiempo tarda cuando crece el tamaño de su entrada.
Entonces, si la entrada es de tamaño N y el algoritmo evalúa una expresión de complejidad constante: O (1) N veces, la complejidad del algoritmo es lineal: O (N). Si la expresión tiene complejidad lineal, el algoritmo tiene una complejidad cuadrática: O (N * N).
Algunas expresiones tienen una complejidad exponencial: O (N ^ N) o complejidad logarítmica: O (log N). Para un algoritmo con bucles y recursividad, multiplique las complejidades de cada nivel de bucle y / o recursión. En términos de complejidad, el bucle y la recursividad son equivalentes. Un algoritmo que tiene diferentes complejidades en diferentes etapas en el algoritmo, elige la mayor complejidad e ignora el resto. Y finalmente, todas las complejidades constantes se consideran equivalentes: O (5) es lo mismo que O (1), O (5 * N) es lo mismo que O (N).
En general, decidir la complejidad del algoritmo es teóricamente imposible.
Sin embargo, un método genial y centrado en el código para hacerlo es realmente pensar en términos de programas directamente. Toma tu ejemplo:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
}
}
Ahora queremos analizar su complejidad, así que agreguemos un contador simple que cuente el número de ejecuciones de la línea interna:
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
counter++;
}
}
Como la línea System.out.println en realidad no importa, eliminemosla:
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
counter++;
}
}
Ahora que solo tenemos el contador a la izquierda, obviamente podemos simplificar el bucle interno:
int counter = 0;
for (int i = 0; i < n; i++) {
counter += n;
}
... porque sabemos que el incremento se ejecuta exactamente n veces. Y ahora vemos que el contador se incrementa en n exactamente n veces, por lo que simplificamos esto para:
int counter = 0;
counter += n * n;
Y surgimos con la complejidad (correcta) O (n 2 ) :) Está ahí en el código :)
Veamos cómo funciona esto para una calculadora recursiva de Fibonacci:
int fib(int n) {
if (n < 2) return 1;
return fib(n - 1) + fib(n - 2);
}
Cambie la rutina para que devuelva el número de iteraciones gastadas dentro de ella en lugar de los números reales de Fibonacci:
int fib_count(int n) {
if (n < 2) return 1;
return fib_count(n - 1) + fib_count(n - 2);
}
¡Todavía es Fibonacci! :) Así que ahora sabemos que la calculadora de Fibonacci recursiva es de complejidad O (F (n)) donde F es el número de Fibonacci en sí.
Ok, veamos algo más interesante, digamos mergesort simple (e ineficiente):
void mergesort(Array a, int from, int to) {
if (from >= to - 1) return;
int m = (from + to) / 2;
/* Recursively sort halves */
mergesort(a, from, m);
mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
}
for (i = from; i < to; i++)
a[i] = b[i - from];
}
Como no estamos interesados en el resultado real sino en la complejidad, cambiamos la rutina para que realmente devuelva el número de unidades de trabajo realizadas:
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
count++;
}
for (i = from; i < to; i++) {
count++;
a[i] = b[i - from];
}
return count;
}
Luego eliminamos aquellas líneas que en realidad no impactan los conteos y simplificamos:
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
count += to - from;
/* Copy the array */
count += to - from;
return count;
}
Todavía simplificando un poco:
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
count += (to - from) * 2;
return count;
}
Ahora podemos prescindir de la matriz:
int mergesort(int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(from, m);
count += mergesort(m, to);
count += (to - from) * 2;
return count;
}
Ahora podemos ver que en realidad los valores absolutos de from y to no importan más, pero solo su distancia, entonces lo modificamos a:
int mergesort(int d) {
if (d <= 1) return 1;
int count = 0;
count += mergesort(d / 2);
count += mergesort(d / 2);
count += d * 2;
return count;
}
Y luego llegamos a:
int mergesort(int d) {
if (d <= 1) return 1;
return 2 * mergesort(d / 2) + d * 2;
}
Aquí, obviamente, d en la primera llamada es el tamaño de la matriz que se ordenará, por lo que tiene la recurrencia para la complejidad M (x) (esto está a la vista en la segunda línea :)
M(x) = 2(M(x/2) + x)
y esto debes resolverlo para llegar a una solución de formulario cerrada. Esto lo hace más fácil adivinando la solución M (x) = x log x, y verifique para el lado derecho:
2 (x/2 log x/2 + x)
= x log x/2 + 2x
= x (log x - log 2 + 2)
= x (log x - C)
y verificar que sea asintóticamente equivalente al lado izquierdo:
x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x
Me gusta usar dos cosas para la notación de Big-O: estándar de Big-O, que es el peor de los casos, y promedio de Big-O, que es lo que normalmente termina sucediendo. También me ayuda a recordar que la notación Big-O está tratando de aproximar el tiempo de ejecución en función de N, el número de entradas.
El TA explicó esto con algo así como combinaciones. De esta manera, n elige 2 = (n (n-1)) / 2 = n ^ 2 + 0.5, luego elimina la constante para que se convierta en n ^ 2. Puedo poner valores de prueba int y probar, pero ¿cómo entra esta combinación?
Como dije, el gran O normal es el peor de los casos. Puede tratar de contar el número de veces que se ejecuta cada línea, pero es más simple mirar el primer ejemplo y decir que hay dos bucles sobre la longitud de n, uno incrustado en el otro, entonces es n * norte. Si fueran uno después del otro, sería n + n, lo que equivale a 2n. Como es una aproximación, solo dices n o lineal.
¿Qué pasa si hay una declaración if? ¿Cómo se determina la complejidad?
Aquí es donde para mí tener un caso promedio y el mejor caso me ayuda mucho a organizar mis pensamientos. En el peor de los casos, ignoras el si y dices n ^ 2. En el caso promedio, para su ejemplo, tiene un ciclo sobre n, con otro ciclo sobre parte de n que ocurre la mitad del tiempo. Esto te da n * n / x / 2 (la x es cualquier fracción de n que se enrolla en tus bucles incrustados. Esto te da n ^ 2 / (2x), por lo que obtendrías n ^ 2 de la misma manera. es porque es una aproximación.
Sé que esta no es una respuesta completa a su pregunta, pero con suerte arroja algún tipo de luz sobre la aproximación de complejidades en el código.
Como se ha dicho en las respuestas anteriores, no es posible determinar esto para todos los fragmentos de código; Solo quería agregar la idea de usar el caso medio de Big-O a la discusión.
Para el primer fragmento, es simplemente n ^ 2 porque realiza n operaciones n veces. Si j se inicializó en i , o subió a i , la explicación que publicó sería más apropiada, pero tal como está, no lo es.
Para el segundo fragmento, puede ver fácilmente que la mitad del tiempo se ejecutará el primero y el segundo se ejecutará la otra mitad del tiempo. Dependiendo de lo que hay allí (con suerte depende de n ), puede volver a escribir la ecuación como recursiva.
Las ecuaciones recursivas (incluido el tercer fragmento) se pueden escribir como tales: la tercera aparecería como
T(n) = T(n-1) + 1
Lo que podemos ver fácilmente es O (n).