Анализ больших О для экспоненциальной функции

Question

Для приведенной ниже функции,

Я сделал

Но я, должно быть, сделал неправильно ... ответитьдолжно быть O(log n).Я ужасен в Большом О ... еще не полностью понял основную теорему, которой еще не учили в школе.Учили только рекурсивное дерево

Answer 1

Если мы предположим, что все арифметические операции выполнены в O (1), то: Как мы видим каждый вызов функции, мы делим exp на 2. Когда мы достигаем нуля с помощью exp - мы выполняем.Сколько раз мы можем разделить exp на два, не достигая нуля?Это журнал опыта.Таким образом, функция log exp вызывает * O (1), что усложняет log (exp).Находя сумму геометрической последовательности, вы находите ответ на другую проблему: сколько узлов в полном (где существуют все братья и сестры) дереве с n листьями: предположим, что n = 4:

1'
|_1''
  |_1'''
  |_2'''
|_2''
  |_3'''
  |_4'''

вы находите количество узлов в такихдерево

Answer 2

Предположения, которые вы делаете в начале своей математики, говорят о том, что вы тратите «n» время на вызов функции Exp(n), «n / 2» время на Exp(n/2), «n / 4» время на Exp(n/4) и так далее ...

Но, на самом деле, вы тратите только постоянное O(1) время на каждый вызов функции. Итак, тогда у вас есть log(n) вызовы функций постоянного времени. Попробуйте выполнить остальную часть своей математики с этим исходным предположением и посмотрите, что вы получите.