Theta нотация и худший случай, время Запуска вложенные циклы

Question

Это код, который я должен проанализировать:

i = 1 
while i < n 
    do 
    j = 0; 
    while j <= i 
     do 
      j = j + 1 
    i = 2i 

Таким образом, первый цикл должен запустить журнал (2, п) и внутренний цикл должен выполняться журналом (2 , n) * (i + 1), но я уверен, что это неправильно. Как использовать тета-нотацию, чтобы доказать это?

Answer 1

Вы не можете использовать i в своем окончательном выражении; только n.

Вы можете легко видеть, что внутренний цикл выполняет i раз каждый раз, когда он достигнут. И похоже, что вы выяснили разные значения, которые могут иметь i. Так что добавьте эти значения, и у вас есть общая работа.

Answer 2

интуитивный способ думать об этом, чтобы увидеть, как много работы вашей внутренней петля делает для фиксированного значения внешнего переменного цикла i. Это явно целых i. Таким образом, если значение i равно 256, то тогда вы будете делать j = j + 1, что много раз.

Таким образом, общая выполненная работа представляет собой сумму значений, которые i принимает во внешнем цикле выполнение. Эта переменная растет очень быстро, чтобы догнать n. Его значения, заданные i = 2i (это должно быть i = 2*i), будут следующими: 2, 4, 8, 16, ..., потому что мы начинаем с 2 итераций внутреннего контура, когда i = 1. Это геометрический ряд: a, ar, ar^2 ... с a = 1 и r = 2. Последний термин, как вы выяснили, будет n, и в серии будет log2 n. И это простое суммирование геометрического ряда.

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

Хронометраж то есть sum of geometric series (a.(r^num_terms - 1)/(r-1)):

T(n) = 2 + 4 + ... 2^(log2 n) 
    = 2 . (2^log2 n - 1) 
    = 2 . (n - 1) 
    ⩽ 3n = O(n) 

Таким образом, вы не можете делать работу, которая является более некоторой константы п. Следовательно, время работы этого алгоритма составляет O(n).

Вы не можете выполнять какую-либо работу, которая меньше некоторой (другой) константы, кратной n, так как вам нужно пройти через инкремент во внутреннем цикле, как показано выше. Таким образом, время выполнения этого алгоритма также равно ≥ c.n, то есть Ω(n).

Вместе это означает, что время работы этого алгоритма равно Θ(n).