tiempo resueltos programa espacio ejercicios ejemplos ejecucion complejidad calcular analisis algoritmos algoritmo c algorithm time-complexity

resueltos - tiempo de ejecucion de un algoritmo en java



¿Cuál es la complejidad temporal de mi función? (4)

Comencé a estudiar sobre la complejidad, estoy luchando con este:

void what(int n) { int i; for (i = 1; i <= n; i++) { int x = n; while (x > 0) x -= i; } }

Bueno, el primer bucle for es claramente O(n) . La primera iteración es O(n) , la segunda es O(n/2) ... ¿y al igual que log(n) veces, supongo? Lo que significa O(n) * O(log(n)) = O(n * log(n)) complexity . ¿Lo entendí bien?

Editar: (no es un duplicado) Sé lo que es Big O. He pedido la evaluación correcta en un caso específico.

Como alternativa, use una sustitución de variables y = n - x seguida de la notación Sigma para analizar el número de iteraciones del bucle while interno de su algoritmo.

Lo anterior sobreestima, para cada bucle while interno, el número de iteraciones en 1 para los casos en que n-1 no es un múltiplo de i , es decir, donde (n-1) % i != 0 . A medida que avanzamos, asumiremos que (n-1)/i es un número entero para todos los valores de i , por lo tanto, sobreestimamos el número total de iteraciones en el bucle while interno, incluyendo posteriormente el signo menor o igual en (i) continuación . Procedemos con el análisis de notación Sigma:

donde nosotros, en (ii) , hemos aproximado el número n : th armónico por la integral asociada. Por lo tanto, su algoritmo se ejecuta en O(n·ln(n)) , asintóticamente.

Dejando el comportamiento asintótico y estudiando el crecimiento real del algoritmo, podemos usar los buenos datos de muestra de pares exactos (n,cnt) (donde cnt es el número de iteraciones internas) por @chux (consulte su respuesta), y comparar con el estimado número de iteraciones desde arriba, es decir, n(1+ln(n))-ln(n) . Es evidente que la estimación armoniza perfectamente con el recuento real, vea los gráficos a continuación o este fragmento para los números reales .

Finalmente, tenga en cuenta que si dejamos n->∞ en la suma sobre 1/i anterior, la serie resultante es la serie armónica infinita , que curiosamente es divergente. La prueba de esto último hace uso del hecho de que, en suma infinita de términos distintos de cero, naturalmente es infinito en sí mismo. En la práctica, sin embargo, para un n suficientemente grande pero no infinito , ln(n) es una aproximación apropiada de la suma, y ​​esta divergencia no es relevante para nuestro análisis asintótico aquí.

El bucle externo se ejecuta n veces.

Para cada iteración, los bucles internos se ejecutan n / i veces.

El número total de ejecuciones es:

n + n/2 + n/3 + ... + n/n

Asintóticamente (ignorando el redondeo aritmético de enteros), esto se simplifica como

n * (1 + 1/2 + 1/3 + ... + 1/n)

Esta serie converge libremente hacia n * log(n) .

Por lo tanto, la complejidad es O (N.log (N)) como esperaba.

El primer bucle interno se ejecuta n veces
El segundo bucle interno se ejecuta n/2 veces
El tercer ciclo interno corre n/3 veces
.. El último corre una vez

Entonces n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n) .

Esto se multiplica por la suma de series armónicas, que no tiene una buena representación de forma cerrada. Pero como se muestra aquí es O(log(n)) . Entonces, en general, el algoritmo es O(n log(n))

Intentando esto mediante pruebas y gráficos. El gráfico log2 vs log2 parece bastante lineal. Algo entre más de O lineal (n) y menos de O (n * log (n)). "Dibuja" tu propia conclusión.

[Editar]

Usando las fórmulas matemáticas derivadas, el O () calculado es un límite superior de O (n * log (n)). Que utiliza "fracciones de iteraciones de bucle" que aumentan el recuento en una fracción y no 1. Por ejemplo, cuando n es 6, el recuento de iteraciones es 6 + 3 + 2 + 1.5 + 1.2 + 1 = 14.7 bucles en lugar de 6 + 3 + 2 reales + 2 + 2 + 1 = 16. Esta diferencia es relativamente menos significativa a medida que aumenta n , por lo tanto, el crecimiento es ligeramente menor que O (n * log (n)). Entonces, al no ignorar el código que usa matemáticas enteras, tenemos una pregunta mucho más desafiante.

unsigned long long what(int n) { unsigned long long cnt = 0; int i; for (i = 1; i <= n; i++) { int x = n; while (x > 0) { x -= i; cnt++; } } return cnt; } void wtest(int n) { unsigned long long cnt = what(n); printf("%d %llu/n", n, cnt); fflush(stdout); } void wtests(void) { int i = INT_MAX/2 + 1; while (i > 0) { wtest(i); i /= 2; } } int main(void) { wtests(); return 0; }

Salida

1073741824 23567395117 536870912 11411566988 268435456 5519718329 134217728 2666826555 67108864 1286897093 33554432 620190504 16777216 298466265 8388608 143418602 4194304 68802063 2097152 32947406 1048576 15746897 524288 7510048 262144 3573331 131072 1695816 65536 802493 32768 378537 16384 177921 8192 83286 4096 38803 2048 17973 1024 8275 512 3782 256 1713 128 765 64 337 32 145 16 61 8 24 4 9 2 3 1 1