Ho il seguente codice:
int sum = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
for (int k = 1; k <= N; k = k*2)
for (int h = 1; h <= k; h++)
sum++;
Quindi ho calcolato quanto esegue ogni ciclo e poi tutto lo script, e penso che potrei sbagliarmi per l'ultimo.
1. N
2. N
3. 1 + log2N( means log N to the base 2)
4. N
Quindi la quantità totale di esecuzione del ciclo interno sarebbe N ^ 3 * (1 + log2N).
Ho ragione? Come posso trasformare questa affermazione?
UPDATE 1
Ho un'altra soluzione che sembra mostruosa:
1. N
2. N
3. LOG2(N) + 1
4. 2^(LOG2(2N)) - 1
Quindi l'importo totale dei cicli sarebbe n^2 * (LOG2(N) + 1) * 2^(LOG2(2N)) - 1 .
Che si trasforma in n ^ 2 ordine di crescita.
UPDATE 2
Ho scritto una semplice app di test per verificare la mia ipotesi.
sembra che il terzo ciclo sia già calcolato per qualche motivo è il quarto. Almeno questo è il risultato dell'applicazione di test. Ho buttato via (LOG2(N) + 1) .
Come risultato di diverse trasformazioni ho seguito l'equazione per la quantità totale di chiamate sum ++:
N*N*(2*N - 1) = 2 * N^3 - N^2 ~ N^3