формула для суммы n + n / 2 + n / 3 + ... + n / n

Question

так что я получил этот алгоритм, мне нужно рассчитать его сложность времени

, который выглядит как

for i=1 to n do
    k=i
    while (k<=n) do
        FLIP(A[k])
        k = k + i

, где A - массив логических значений, а FLIP, как есть, переворачивает текущее значение. следовательно, это O(1).

Теперь я понимаю, что внутренний цикл while должен называться

n/1+n/2+n/3+...+n/n

Если я прав, но есть ли формула для такого расчета?

довольно запутан здесь

спасибо!

Answer 1

Допустим, мы хотим вычислить сумму этого уравнения

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

Тогда в скобках (1 + 1/2 + 1/3 + ... + 1 / n) это хорошо известная гармоническая серия , и я боюсь, что есть нет проверенной формулы для расчета гармонического ряда.

Answer 2

Более точное вычисление составляет T(n) \sum((n-i)/i) для i = 1 to n (потому что k начинается с i). Следовательно, окончательная сумма составляет n + n/2 + ... + n/n - n = n(1 + 1/2 + ... + 1/n) - n, примерно. Мы знали 1 + 1/2 + ... + 1/n = H(n) и H(n) = \Theta(\log(n)). Hence, T(n) = \Theta(n\log(n)). -n никак не влияет на асимптотические вычислительные затраты, как n = o(n\log(n)).