Algoritmo de Análise de Três de ciclo aninhado

Question

Eu estou tentando descobrir como função do Tempo e Big O de um loop aninhado código,

public static int example5(int[ ] first, int[ ] second) { // assume equal-length arrays
  int n = first.length, count = 0;
  for (int i=0; i < n; i++) { // loop from 0 to n-1
    int total = 0;
    for (int j=0; j < n; j++) // loop from 0 to n-1
      for (int k=0; k <= j; k++) // loop from 0 to j
      total += first[k];
  if (second[i] == total) count++;
}
  return count;
}

De acordo com meus cálculos o tempo de função deve estar no $n^4$, mas a resposta certa é $n^3$.
Aqui estão os meus passos solução,

1. Constante operações = 2 vezes
   
2. i-loop = 0 a n-1 = n vezes (embora 2n+2, mas eu escolheria a mais alta ordem a prazo)
   
3. A operação constante = 1 hora
   
4. j-loop = 0 a n-1 = n x n vezes = $n^2$ vezes
5. k-loop = 1+2+3+...+n-1+n = n x n x $n\frac{n+1}{2}$ vezes = $\frac{n^4 + n^3}{2}$ vezes

O que eu estou fazendo de errado, alguém por favor pode apontar.

Answer 1

Três loops você fica para n^3.

EDITAR:

for (int i=0;eu < n;i++) // primeiro n ..etc..for (int j=0;j < n;j++) // segundo n ...etc...

Duas exteriores são n, que faz com que n^2 até agora.Em seguida olhar loop interno:

for (int k=0;k <= j;k++) // terceiro n

Íntimo conta como outra n para big O, mesmo se a execução de k para j em vez de k para n.Você ainda está na ordem dos n^3.

Para que o loop interno que você está fazendo 1 + 2 + 3 ...loops como j repete-se, assim, estritamente falando, não é exatamente n^3 iterações, mas n * n * (n+1)/2, mas para grande S de fins não deixe que jogá-lo fora, é n^3, o (n+1)/2 peça é apenas uma outra camada de n.Se n foi de 1.000.000 você vai acabar com "no fim dos" 10^18 loops.

Espero que isso ajude.