Блог пользователя Dumbledore

Dumb question on time complexity
Автор Dumbledore, история, 9 лет назад, По-английски 
for (int i = 1; i <= MAXN; i++)
     for (int j = i; j <= MAXN; j += i);


Can anybody explain to me why the time complexity for this code is O(N log N)?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

The time complexity is O(N + N/2 + N/3 + N/4 + ... + N/N) = O(N*(1 + 1/2 + 1/3 + ... + 1/N)).

But 1 + 1/2 + 1/3 + ... 1/N < log(N). (link)

=> O(N + N/2 + N/3 + N/4 + ... + N/N) = O(N*(1 + 1/2 + 1/3 + ... + 1/N)) = O(N*log(N)).

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

[Link](https://en.m.wikipedia.org/wiki/Harmonic_series_(mathematics)) divergence -> integral test

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Already answered twice, but still:

For the number of iterations (complexity) you have the sum :

Where Hn is the sum of the first n terms of the Harmonic series. Generally the harmonic series differs by a constant factor from the natural logarithm, more precisely, if n tends towards infinity then the difference Hn - ln(n) tends towards the Euler-Mascheroni constant which has a value of about 0.577, hence we get that the complexity is O(NlnN) = O(NlogN)

→ Ответить