2. Будет ли этот способ экспоненциальным? Да, будет, по определению показательной функции с основанием больше 1.
Видимо, можно точно подсчитать, чему равно основание.
Это правда - относительно самого очевидного метода -> f(n-2)+f(n-1)
3. Самый простой и естественный способ - вычислять в цикле за время O(n), запоминая только два предыдущих значения.
Правильно ты все пишешь в третьем пункте, его то мы и обсуждаем, и сложность этого алгоритма, про который ты пишешь в 3 пункте esperanto оценил в O(2^N). Можете перечитать.
