Как рассчитать сложность времени для функции ниже?

Question

Какова временная сложность функции ниже?

void function(int n){ 
     for(int i=0; i<n; i++){. //n times 
      for(int j=i ; j< i*i; j++){ // n*n times 
       if(j%i == 0){ 
        for(int k=0; k<j; k++){ // j times = n * n times. 
         ++counter; 
        } 
       } 
      } 
     } 
    } 

Книга говорит O(n^5). Но я не мог понять, почему книга не учитывала j%i. На основании этого определяется петля k. Вы можете уточнить?

Answer 1

Рассмотрим часть кода, в которой и есть сомнения:

for(int j=i ; j< i*i; j++) 
{ 
    if(j%i == 0) 
     { 
       for(int p=0; p<j; p++){ 
       ++counter; 
     } 
     } 

Давайте проанализируем эту часть кода. Для каждого i, j%i==0 будет справедливо, когда j кратно i, т.е.

i, 2i, 3i, .... i*i // upto i*i only,since j<i*i 

Теперь для каждого j, внутри сложность O(j).

Так Сложность этой части коды:

Таким образом, общая сложность = O(n*n^3) = O(n^4)

Answer 2

В самом деле, функция работает во время О (п^4), так как if состояние бывает только один раз примерно n петли. См. Ниже для точного анализа.

void function (int n) { 
    for(int i=0; i<n; i++) { 
     // Runs a total of n times 
     for(int j=i; j< i*i; j++) { 
      // Runs a total of (n^3 - n)/3 = O(n^3) times 
      if(j%i == 0) { 
       // Runs a total of (n^2 - n)/2 = O(n^2) times 
       for(int k=0; k<j; k++) { 
        // Runs a total of (3n^4 - 10n^3 + 9n^2 - 2n)/24 = O(n^4) times 
        ++counter; 
       } 
      } 
     } 
    } 
}