Member 11048734 Ответов: 1

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

int fun(int n) 
 {
 if (n <= 1)
 return 1;
 return fun(n-1) + fun(n-2);
 }


Что я уже пробовал:

int fun2(int n)
{
	if (n <= 1) return n;
	return fun2(n-1) + fun2(n-1);
}

временная сложность для этого кода составляет:::
O (2^n)
В этой функции код возврата fun2(П-1) + fun2(П-1) я.е.оба же
Но как найти временную сложность, если и то и другое различно

1 Ответов

Рейтинг:
1

Patrice T

Этот код яростно похож на рекурсивную функцию Фибоначчи.
Поскольку код в функции очень прост, время и сложность в основном зависят от количества вызовов функций.
Проще всего сделать подсчет вызовов функций.
Объявите глобальную переменную для использования в качестве счетчика, добавьте строку в функцию, которая увеличивает значение при каждом вызове.
Затем соберите количество вызовов для каждого значения n, составьте таблицу со значением и сравните, как количество вызовов эволюционирует с каждым n.