Как внутренний цикл выполнялся "n / i" раз?

Question

У меня есть сомнения относительно временной сложности фрагмента кода, и я не совсем понял данное решение.

function (n) {
           for(int i =0 ; i < n ; i ++){
                       for(int j = 0 ; j <= n ; j += i){
                                  printf("*");
                                      }

В приведенном выше коде задано, что внутренний цикл выполняется n/i раз для каждого значения i.Общая сложность времени составляет O(nlogn).

Я не могу понять, почему внутренний цикл выполняется n/i раз.Может кто-нибудь, пожалуйста, помогите мне.

Answer 1

Существует два цикла, один с приращением i, а другой с приращением j.

При фиксированном i для каждого прохода цикла j, j увеличивается на i, пока j не достигнет n.

Таким образом, значения j в каждой итерации:

j
j + i
j + 2i
...
j + (n/i - j/i)i 

Как вы можете видеть, это запускается O (н / я) раз.