Зараз я вивчаю структури даних в університеті і натрапив на питання про складність рекурсії.
Даний код:
Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;
\do somthing(in O(1) )
return func(n-1) + func(n-1);
}
Я знаю, що робить код. Я знаю, що у формі, яка є зараз, складність часу становить O (2 ^ n).
Однак моє запитання: чи зміниться складність часу, якщо замість останнього зворотного виклику коду я напишу: return 2*func(n-1) ?
Я знаю, що, що стосується складності пам'яті, ми говоримо про значне зменшення простору, зайнятого рекурсією, але що стосується складності часу, чи відбудуться якісь зміни?
Я прорахував математику, використовуючи рекурсивну функцію, і прийшов до розуміння, що не буде змін у складності часу, чи не так?
Відповіді:
4 для відповіді № 1Цей метод має лише O(n), тому що якщо ви запускаєте його з 5, він переходить до рекурсії з 4, потім з 3 і т.д.
Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;
\do somthing(in O(1) )
return 2*func(n-1);
}
Однак як щодо цього:
Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;
\do somthing(in O(1) )
return func(n-1) + func(n-1);
}
Наприклад, наприклад, func (5) він виконується спочатку наступним чином
5 -> 4 -> 3 -> 2 -> 1
Потім він повертається до 2, але там він виконає «другу» частину, тож весь процес виглядає так
5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.
Тому це РІЗНО змінює складність від O(n) до O(2^n)
Давайте спробуємо на практичному прикладі цей код:
public class Complexity {
private static int counter;
public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
counter = 0;
func(i);
System.out.println("For n="+i+" of 2*func the number of cycles is " + counter);
counter = 0;
func2(i);
System.out.println("For n="+i+" of func + func the number of cycles is " + counter);
}
}
public static int func(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return 2 * func(n - 1);
}
public static int func2(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return func2(n - 1) + func2(n - 1);
}
}
Маючи цей результат:
For n=0 of 2*func the number of cycles is 1
For n=0 of func + func the number of cycles is 1
For n=1 of 2*func the number of cycles is 1
For n=1 of func + func the number of cycles is 1
For n=2 of 2*func the number of cycles is 2
For n=2 of func + func the number of cycles is 3
For n=3 of 2*func the number of cycles is 3
For n=3 of func + func the number of cycles is 7
For n=4 of 2*func the number of cycles is 4
For n=4 of func + func the number of cycles is 15
For n=5 of 2*func the number of cycles is 5
For n=5 of func + func the number of cycles is 31
For n=6 of 2*func the number of cycles is 6
For n=6 of func + func the number of cycles is 63
For n=7 of 2*func the number of cycles is 7
For n=7 of func + func the number of cycles is 127
For n=8 of 2*func the number of cycles is 8
For n=8 of func + func the number of cycles is 255
For n=9 of 2*func the number of cycles is 9
For n=9 of func + func the number of cycles is 511
For n=10 of 2*func the number of cycles is 10
For n=10 of func + func the number of cycles is 1023
For n=11 of 2*func the number of cycles is 11
For n=11 of func + func the number of cycles is 2047
For n=12 of 2*func the number of cycles is 12
For n=12 of func + func the number of cycles is 4095
For n=13 of 2*func the number of cycles is 13
For n=13 of func + func the number of cycles is 8191
For n=14 of 2*func the number of cycles is 14
For n=14 of func + func the number of cycles is 16383
For n=15 of 2*func the number of cycles is 15
For n=15 of func + func the number of cycles is 32767
For n=16 of 2*func the number of cycles is 16
For n=16 of func + func the number of cycles is 65535
For n=17 of 2*func the number of cycles is 17
For n=17 of func + func the number of cycles is 131071
For n=18 of 2*func the number of cycles is 18
For n=18 of func + func the number of cycles is 262143
For n=19 of 2*func the number of cycles is 19
For n=19 of func + func the number of cycles is 524287
Але якщо ви пам’ятаєте вже обчислені результати, складність все ще залишається O(n) навіть при другому підході:
public class Complexity {
private static int counter;
private static int[] results;
public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
counter = 0;
func(i);
System.out.println("For n="+i+" of 2*func the number of cycles is " + counter);
counter = 0;
func2(i);
System.out.println("For n="+i+" of func + func the number of cycles is " + counter);
counter = 0;
results = new int[i+1];
func3(i);
System.out.println("For n="+i+" of func + func with remembering the number of cycles is " + counter);
}
}
public static int func(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return 2 * func(n - 1);
}
public static int func2(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return func2(n - 1) + func2(n - 1);
}
public static int func3(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
if (results[n] == 0){
results[n] = func3(n - 1) + func3(n - 1);
}
return results[n];
}
}
Маючи цей результат:
For n=0 of 2*func the number of cycles is 1
For n=0 of func + func the number of cycles is 1
For n=0 of func + func with remembering the number of cycles is 1
For n=1 of 2*func the number of cycles is 1
For n=1 of func + func the number of cycles is 1
For n=1 of func + func with remembering the number of cycles is 1
For n=2 of 2*func the number of cycles is 2
For n=2 of func + func the number of cycles is 3
For n=2 of func + func with remembering the number of cycles is 3
For n=3 of 2*func the number of cycles is 3
For n=3 of func + func the number of cycles is 7
For n=3 of func + func with remembering the number of cycles is 5
For n=4 of 2*func the number of cycles is 4
For n=4 of func + func the number of cycles is 15
For n=4 of func + func with remembering the number of cycles is 7
For n=5 of 2*func the number of cycles is 5
For n=5 of func + func the number of cycles is 31
For n=5 of func + func with remembering the number of cycles is 9
For n=6 of 2*func the number of cycles is 6
For n=6 of func + func the number of cycles is 63
For n=6 of func + func with remembering the number of cycles is 11
For n=7 of 2*func the number of cycles is 7
For n=7 of func + func the number of cycles is 127
For n=7 of func + func with remembering the number of cycles is 13
For n=8 of 2*func the number of cycles is 8
For n=8 of func + func the number of cycles is 255
For n=8 of func + func with remembering the number of cycles is 15
For n=9 of 2*func the number of cycles is 9
For n=9 of func + func the number of cycles is 511
For n=9 of func + func with remembering the number of cycles is 17
For n=10 of 2*func the number of cycles is 10
For n=10 of func + func the number of cycles is 1023
For n=10 of func + func with remembering the number of cycles is 19
For n=11 of 2*func the number of cycles is 11
For n=11 of func + func the number of cycles is 2047
For n=11 of func + func with remembering the number of cycles is 21
For n=12 of 2*func the number of cycles is 12
For n=12 of func + func the number of cycles is 4095
For n=12 of func + func with remembering the number of cycles is 23
For n=13 of 2*func the number of cycles is 13
For n=13 of func + func the number of cycles is 8191
For n=13 of func + func with remembering the number of cycles is 25
For n=14 of 2*func the number of cycles is 14
For n=14 of func + func the number of cycles is 16383
For n=14 of func + func with remembering the number of cycles is 27
For n=15 of 2*func the number of cycles is 15
For n=15 of func + func the number of cycles is 32767
For n=15 of func + func with remembering the number of cycles is 29
For n=16 of 2*func the number of cycles is 16
For n=16 of func + func the number of cycles is 65535
For n=16 of func + func with remembering the number of cycles is 31
For n=17 of 2*func the number of cycles is 17
For n=17 of func + func the number of cycles is 131071
For n=17 of func + func with remembering the number of cycles is 33
For n=18 of 2*func the number of cycles is 18
For n=18 of func + func the number of cycles is 262143
For n=18 of func + func with remembering the number of cycles is 35
For n=19 of 2*func the number of cycles is 19
For n=19 of func + func the number of cycles is 524287
For n=19 of func + func with remembering the number of cycles is 37
2 для відповіді № 2
Це залежить від семантики вашої мови програмування / алгоритму.
Якщо по f(n) ви маєте на увазі "викликати функцію незалежно від того, чи була вонавикликається з тим самим аргументом перед "(як це відбувається у більшості мов програмування), тоді ваша зміна різко зменшить складність до O (n). У вас є один виклик функції O (1) на зменшення аргументу.
В іншому випадку (якщо ви говорите про чисті функції та запам'ятовування відомих результатів), обидва алгоритми вже мають складність O (n).