Определение временной сложности этих вложенных циклов
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), но как мне получить то, что мне нужно, из внутреннего цикла?
Ответы 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)
Что ж, внешний цикл, очевидно, будет выполнять итерации 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 является некоторым постоянным фактором, и, используя правила большого O, нас не волнует часть log(n), потому что у нас есть часть n, поэтому это просто O(n).