Рекуррентное соотношение и сложность времени

Question

Что такое отношение повторения и сложность времени для следующего псевдокода?

temp = 1 
repeat 
    for i=1 to n 
        temp = temp +1 
    n=n/2
until n>=1

Answer 1

Когда мы имеем дело с асимптотическими обозначениями, такими как Big-Oh, Omega и Theta, мы не учитываем константы.Без сомнения, ваша временная сложность пойдет как

    n + n/2 + n/4 + ... + 1

, но если вы добавите эту уменьшающуюся серию GP, вы получите точный ответ, равный c * n, где c будет некоторой константой, большей 1. Но в асимптотических обозначенияхКак я уже говорил ранее, константы не имеют значения, поэтому значение c равно 2, или 50, или 100, или 10000, или чему-то еще, это будет только O (n).

Другое дело, старайтесь не использовать теорему Мастерадля решения рекуррентных отношений и использования метода Рекурсивного Дерева, поскольку он является чисто концептуальным и поможет вам в построении ваших концепций и может быть использован в любом случае.Теорема магистра похожа на сокращение и также имеет ограничения.