У меня есть программа, как это на лабораториивычислительная сложность рекурсии
int fun(int n)
{
if (n==0) return 0;
else return fun(n-1) +1;
}
и профессор сказал, что функция O (2^п). Не могу понять, почему, каждый раз, когда я рассчитываю O, я получаю O (n)
Кто-нибудь может объяснить это мне?
int fun(int n)
{
if (n==0) return 0; //1 operation for the base case
else return fun(n-1) +1; //n-1 operation in total
}
мы можем смотреть на него в обратном направлении, позволяет сказать, что вы находитесь в базовом случае теперь вы будете делать один return 0; что O (1), а затем один уровень выше вы будете return 0+1;, который также является O (1). Сколько раз вы собираетесь вернуться? ну, ответ прост, n раз, поэтому n * 1 = n => O (n). если вы хотите быть точным, вы делаете одно сравнение, одно добавление и один возврат каждый раз, когда вы возвращаетесь, так что это делает 3 * n - 1 в общей сложности, который все еще равен O (n)
это O (n) ... ваш профессор ошибается, LOL ... какой университет кстати? – Steve
теперь есть простой способ проверить, кто прав, для простых вопросов, подобных этому, вы можете просто подставить в некоторых числах и подсчитать количество операций, O (2^n) означает, что он всегда будет больше, чем c * 2^п. в этом примере c не может быть <1, поэтому, если вы добавите в 10, вы можете видеть, что это явно не так. – Steve
Ну «вот так» может быть опасно. Какую проблему вы решаете с помощью метода рекурсии? (конечно, в этом методе вы правы, это O (n)). – libik