Определение временной сложности этих вложенных циклов

Question

for i = 1 to n do
    j = i
    while j < n do
        j = 2 * j

Ответ, который я получил, - O (n), потому что сумма от i = 1 до n из 1 + log (n / i) - это количество выполнений. Может ли кто-нибудь объяснить, как прийти к такому выводу? Я знаю, что внешние циклы запускаются O (n), но как мне получить то, что мне нужно от внутреннего цикла?

Answer 1

Ну, внешний цикл, очевидно, будет выполнять n итераций.

То, что делает внутренний цикл, в основном умножает j на 2, тогда как оно меньше n, поэтому для первой итерации j=1 оно умножит его 1 + log(n) в худшем случае. Для более общего случая j=i, где 1 <= i < n вам потребуется 1 + log(n)-log(i) раз (поскольку вы начинаете не с 1, а с i). 1 + log(n)-log(i)= 1 + log(n/i).

Таким образом, в целом у вас есть O(sum (1 + log(n/i)) from 1 to n), который в конечном итоге равен , равному O(n + c*log(n)), где c - некоторый постоянный коэффициент, и, используя правила big-O, нас не волнует log(n) часть, потому что у нас есть n часть, так что это просто O(n).

Answer 2

Вы в конечном итоге с

        n
T(n) = Sum ( log(n/i) )
       i=1

        n
     = Sum ( log(n) - log(i) )
       i=1

    =  n log n - log(n!)

Используйте Формула Стерлинга , чтобы заменить log(n!) = n log n - n + O(log n)

T(n) = n - O(log n) = O(n)