Какова временная сложность этого кода?Мой учитель и я не могу согласиться

Question

Я получил этот кусок кода (функция).

Если я запускаю его с n = 10, он вызывается в общей сложности 2047 раз в соответствии с runCounter. Если я запускаю его с n = 20, то до завершения он вызывается в общей сложности 2 097 151 раз.

По словам моего учителя, этот код имеет временную сложность O (n ^ 2), но я не могу понять, почему. 10 ^ 2 = 100. Нигде около 2047 и 20 ^ 2 = 400, еще больше ошибок. Я думаю, что этот код больше соответствует O (2 ^ n), потому что 2 ^ 10 = 1024 и 2 ^ 20 = 1 048 576, что больше соответствует поведению функции. Я прав или мой учитель прав?

Есть ли простой способ решения этих проблем? Я пытаюсь написать стек вызовов на бумаге и получить представление о том, что происходит, но это наглядно, как мне написать это в чисто математических терминах?

Answer 1

Сложность на самом деле кажется O(2^(n+1)).Вызовы методов, выполняемые в вашей рекурсивной функции, примут форму сбалансированного двоичного дерева, высота которого n + 1, для входа n.

С такой проблемой, как хорошая компьютерная наукаПодход заключается в том, чтобы просто записать количество вызовов методов.Для ввода n = 5 вот как выглядит число вызовов методов:

n=5 -> n=4, n=4 (2 calls)

n=4 -> n=3, n=3 (4 calls)
n=4 -> n=3, n=3

n=3 -> n=2, n=2 (8 calls)
n=3 -> n=2, n=2
n=3 -> n=2, n=2
n=3 -> n=2, n=2

n=2 -> n=1, n=1 (16 calls)
n=2 -> n=1, n=1
n=2 -> n=1, n=1
n=2 -> n=1, n=1
n=2 -> n=1, n=1
n=2 -> n=1, n=1
n=2 -> n=1, n=1
n=2 -> n=1, n=1

n=1 -> (32 calls to n=0, then the recursion ends)

Итак, вызов сгенерированный с n=5:

1 + 2 + 4 + 8 + 16 + 32 = 63 calls

Это эквивалентно:

2^(5+1) - 1 = 2^(n+1) - 1

Итак, сложность на самом деле O(2^(n+1)), а не O(n^2). Вот ссылка на страницу Википедии, которая также показывает ту же формулу для числа узлов в сбалансированном двоичном дереве.