Выяснение большого размера (o)

Question

for (int i = 0; i < n; i++) 
     { 
      for (int j = 0; j < i*i; j++) 
      { 
       cout << j << endl; 
       result++; 
      } 
     } 

Выполнение этого действия означает, что он рассчитан на 5 человек в общей сложности 30 раз. Я знаю, что внешняя петля работает N. Внутренняя петля, хотя и дает мне некоторую проблему, поскольку она не n*n, а i*i, и я не видел такого, как это, прежде чем пытаться выяснить, T(n) и Big (O).

Answer 1

Этот алгоритм O(n^3): Для того, чтобы понять это, мы должны выяснить, как часто внутренний код

cout << j << endl; 
result++; 

выполняется. Для этого нам нужно подвести итог 1*1+2*2+...+n*n = n^3/3+n^2/2+n/6, который является хорошо известным результатом (см., Например, Sum of the Squares of the First n Natural Numbers). Таким образом, O(T(n)) = O(1*1+2*2+...+n*n) = O(n^3) и (время) сложности алгоритма, следовательно, O(n^3).

Edit: Если вы задаетесь вопросом, почему это достаточно (см также пример 4 в Time complexity with examples) полезно переписать код, как единый контур таким образом, мы можем видеть, что петли добавить постоянное количество инструкций (для каждого запуска внутреннего кода):

int i = 0; 
int j = 0; 

while(i < n) { 
    cout << j << endl; 
    result++; 
    if(j < i * i) j++; //were still in the inner loop 
    else {//start the next iteration of the outer loop 
     j = 0; 
     i++; 
    } 
} 

Таким образом, две петли «добавить» два сравнения плюс условный оператор, который просто делает условные переходы и их последствия более явным.