Почему временная сложность метода рекурсии для вычисления ряда Фибоначчи составляет 2 ^ n, а не 2 ^ n ^ 2?

Question

Я наткнулся на это как на хороший пример для понимания времени выполнения рекурсивно вызываемых функций.Здесь есть хорошее описание проблемы: https://stackoverflow.com/a/33663627/9750088

Однако мое недоразумение исходит из суммирования 2 ^ 1 + 2 ^ 2 .... 2 ^ n-1 как суммы каждого уровнявызовы дерева рекурсии.Для меня эта сумма 1 + 2 ... n-1, по-видимому, равна n (n-1) / 2, что мне интуитивно кажется, что n ^ 2 в большой записи O, поэтому приводит к общему времени выполнения O 2^ n ^ 2 в большой) записи.Как именно эта сумма листьев дерева заканчивается 2 ^ n вместо этого?

Answer 1

Мое понимание ответа в этой ссылке:

1. Сначала вы должны понять, сколько узлов в этом дереве рекурсии.Для числа n в дереве есть 2^(n-1) листьев и 2^(n-1)-1 узлов без листьев. (Для корневого уровня есть 2^0 узлов; второй уровень: 2^1 узлов; ...последний неконечный уровень - второй самый низкий уровень: 2^(n-2) узлов. Сумма 2^0+2^1+...+2^(n-2)=2^(n-1)-1. Это важно, вы можете попытаться найти какой-нибудь пример и разобраться в нем.).Таким образом, всего 2^(n-1)+2^(n-1)-1 узлов.
2. Тогда полнота времени равна O(2^(n-1)+2^(n-1)-1)->O(2^(n-1)+2^(n-1))->O(2*2^(n-1))->O(2^n)