Сложность времени для цикла

Question

Внешний цикл выполняется n раз, пока выполняется внутренний цикл? Итак, общее время n * что-то.

Нужно ли мне учиться суммированию, если да, то любая книга для ссылки?

for(int i=1;i<=n;i++) 
    for(int j=1;j<=n;j+=i) 
    printf("*"); 

Answer 1

Я считаю, что сложность времени составляет O(n*log(n)). Вот почему:

Выберем какое-нибудь произвольное натуральное число i и посмотрим, сколько шагов занимает внутренний цикл для данного заданного i. Хорошо для этого i, вы переходите от j = 1 к j < = n с прыжком i между ними. Так что в основном вы делаете это суммирование много шагов:

summation = 1 + (1+i) + (1+2i) + ... (1+ki) 

где к наибольшее целое число такое, что 1 + ки < = п. То есть, k - количество шагов, и это то, что мы хотим решить. Хорошо, мы можем решить для k в равенстве, приводящем к k <= (n-1)/i и таким образом k = ⌊(n-1)/i⌋. То есть, k - это функция пол/целочисленное деление (n-1)/i. Поскольку мы имеем дело со сложностями во времени, эта функция пола не имеет значения, поэтому мы просто скажем k = n/i для простоты. Это число шагов, которые будет выполняться внутренним циклом для данного i. Поэтому мы в основном должны добавить все это для i = 1 в i < = n.

Так numsteps будет это дополнение:

numsteps = n/1 + n/2 + n/3 + ... n/n 
     = n(1 + 1/2 + 1/3 + ... 1+n) 

Так что нам нужно найти сумму 1 + 1/2 + ... 1/п, чтобы закончить это. На эту сумму фактически нет хорошей закрытой формы, но она составляет порядка ln(n). Вы можете узнать больше об этом here. Вы также можете догадаться об этом с integral from 1 to n of 1/x is ln(n). Опять же, поскольку мы имеем дело со сложностью во времени, мы можем просто использовать ln (n) для представления его сложности. Таким образом, мы имеем:

numsteps = n(ln(n)) 

Таким образом, временная сложность O(n*log(n)).

Edit: Мое плохое, я вычислял сумму: P

Answer 2

Этот вопрос можно подойти осмотром:

n = 16 

i | j values   | # terms 
1 | 1, 2, ..., 16 | n 
2 | 1, 3, 5, ..., 16 | n/2 
.. | ..    | n/3 
16 | 16    | n/n 

В приведенной выше таблице, i это значение внешнего контура, и j values показывают итерации внутреннего цикла. По результатам проверки мы увидим, что петли пройдут n * (1 + 1/2 + 1/3 + ... + 1/n) шагов. Это ограниченный гармонический ряд. Как показывает this Math Stack Exchange article, для вышеуказанного выражения нет замкнутой формы в терминах n. Однако, как показывает this SO article, существует верхняя граница O(n*ln(n)).

Итак, время работы для ваших двух петель: O(n*ln(n)).