resueltos - tiempo de ejecucion de un algoritmo en java

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

Question

Esta pregunta ya tiene una respuesta aquí:

• Cómo encontrar la complejidad temporal de un algoritmo 9 respuestas
• Big O, ¿cómo se calcula / aproxima? 23 respuestas
• Finding Big O of the Harmonic Series 2 respuestas

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.

Answer 1

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í.

Answer 2

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.

Answer 3

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))

Answer 4

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