Алоритмическая сложность рекурсивной функции

Question

Вот моя функция.Это просто, я просто не уверен в том, что ответ.

  int calcul( int n) {
    if(n=1)
      return 1;
    else
      return calcul(n/2) + 1;
  }

Теперь, чтобы получить сложность, я делаю:

T (n)= T (n / 2) + O (1)

T (n / 2) = T (n / 4) + O (1)

...

T (1) = O (1)

Теперь, добавляя уравнения, я получаю

T (n) = O (1) + O (1) ...

так, каков окончательный ответ?

Answer 1

Вы выполняете функцию один раз для каждого деления n на 2, то есть log n раз.

Итак, вы получите O(log n).

Edit:

Логарифм (по основанию 2) числа n - это степень, которую 2 необходимо повысить, чтобы получить n.

То есть 2^(log n) = n, где ^ означает возведение в степень.

Теперь простой способ вычислить аппроксимацию log n - это разделить n на 2, тогда как n > 1.

Если вы разделили k раз, вы получите n < 2^k.

Поскольку k - 1 дивизий все еще дают n > 1, у вас также есть n >= 2^(k-1).

Принимая логарифмы на каждого члена 2^(k - 1) <= n < 2^k, вы получаете k - 1 <= log n < k.

Answer 2

Алгоритм очень похож на http://en.wikipedia.org/wiki/Binary_search_algorithm

Итак, вы можете прочитать подробные объяснения, почему это O(log(n))

Answer 3

Дело в том, что каждый раз, когда ваш вход делится на 2, пока он не удовлетворяет условию. ех. н / 2, н / 4, н / 8 .... н / н

Предположим, у вас есть входные данные как 8, тогда этот лог 8, основание два будет 3. Итак, О (логн). Константа не должна учитываться.

Надеюсь, это поможет.

Answer 4

Предлагаю ознакомиться с теоремой Мастера. В этом случае a = 1, b = 2 и f = O (1). Так как f = Theta (1) = Theta (n ^ (log_2 (1) log ^ kn) = Theta (log ^ kn) при k = 0, мы находимся во втором случае теоремы и T (n) = Тета (log ^ (k + 1) n) = Тета (log n).

Очень удобная теорема, полезная в случаях, когда сравнивать с другими алгоритмами и выполнять другие виды анализа не так просто.