¿Cómo calculo la complejidad temporal de la función foo()?

He podido deducir que si k es una potencia de 2, la complejidad temporal es O(logk).

Primero, asumo que el tiempo necesario para cada llamada de función es constante (este no sería el caso, por ejemplo, si el tiempo necesario para una multiplicación depende de los números que se multiplican, como es el caso en algunas computadoras).

También asumimos que k>=1 (de lo contrario, la función se ejecutará sin fin a menos que haya un desbordamiento).

Pensemos el valor k como un número binario:

Si el bit más a la derecha es 0 ( k%2!=0 es falso), el número se desplaza un bit a la derecha ( foo(m,k/2) ) y la función se llama recursivamente.

Si el bit más a la derecha es 1 ( k%2!=0 es verdadero), el bit se cambia a 0 ( foo(m,k-1) ) y la función se llama recursivamente. (Aún no miramos el caso k=1 ).

Esto significa que la función se llama una vez por cada bit y se llama una vez por cada 1 bit. O, en otras palabras: se llama una vez por cada bit 0 en el número y dos veces por cada bit 1 .

Si N es el número de llamadas a funciones, n1 es el número de 1 bits y n0 es el número de 0 bits, obtenemos la siguiente fórmula:

 N = n0 + 2*n1 + C

La constante C ( C=(-1) , si no me equivoqué) representa el caso k=1 que ignoramos hasta ahora.

Esto significa:

 N = (n0 + n1) + n1 + C

Y - porque n0 + n1 = floor(log2(k)) + 1 :

 floor(log2(k)) + C <= N <= 2*floor(log2(k)) + C

Como puede ver, la complejidad del tiempo siempre es O(log(k))

O(registro(k))

Se agregó alguna modificación para generar estadísticas para el gráfico de hoja de cálculo.

 #include <stdio.h> #include <math.h> #ifndef TEST_NUM #define TEST_NUM (100) #endif static size_t iter_count; int foo(int m, int k) { iter_count++; if (k == 0) { return 1; } else if(k == 1) { return m; } else if (k % 2 != 0) { return m * foo(m, k - 1); } else { int p = foo(m, k / 2); return p * p; } } int main() { for (int i = 1; i < TEST_NUM; ++i) { iter_count = 0; int dummy_result = foo(1, i); printf("%d, %zu, %f\n", i, iter_count, log2(i)); } return 0; }

Constrúyelo.

 gcc t1.c -DTEST_NUM=10000 ./a > output.csv

Ahora abra el archivo de salida con un programa de hoja de cálculo y trace las últimas dos columnas de salida.

Para k positivo, la función foo se autodenomina recursivamente p veces si k es la p -ésima potencia de 2. Si k no es una potencia de 2 , el número de llamadas recursivas es estrictamente inferior a 2 * p donde p es el exponente de la mayor potencia de 2 inferior a k .

Aquí hay una demostración:

expandamos la llamada recursiva en el caso k % 2 != 0 :

 int foo(int m, int k) { if (k == 1) { return m; } else if (k % 2 != 0) { /* 2 recursive calls */ // return m * foo(m, k - 1); int p = foo(m, k / 2); return m * p * p; } else { /* 1 recursive call */ int p = foo(m, k / 2); return p * p; } }

El número total de llamadas es floor(log2(k)) + bitcount(k) , y bitcount(k) es por construcción <= ceil(log2(k)) .

No hay bucles en el código y el tiempo de cada llamada individual está limitado por una constante, de ahí la complejidad de tiempo general de O(log k) .