Ich studiere gerade Datenstrukturen an der Universität und stolperte über eine Frage der Komplexität in der Rekursion.
Mit diesem Code:
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);
}
Ich weiß, was der Code tut. Ich weiß, dass in der Form, in der es jetzt ist, die Zeitkomplexität O (2 ^ n) ist.
Meine Frage ist jedoch: Ändert sich die Komplexität der Zeit, wenn ich statt des letzten Rückrufs des Codes schreiben werde: return 2*func(n-1) ?
Ich weiß, dass wir in Bezug auf die Speicherkomplexität von einer signifikanten Reduktion des Platzbedarfs durch die Rekursion sprechen, aber was die zeitliche Komplexität betrifft, wird es Änderungen geben?
Ich rechnete mit einer rekursiven Funktion und kam zu dem Verständnis, dass sich die zeitliche Komplexität nicht ändern wird. Habe ich recht?
Antworten:
4 für die Antwort № 1Diese Methode hat nur O(n), denn wenn du es mit 5 startest, geht es zur Rekursion mit 4, dann mit 3 usw.
Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;
\do somthing(in O(1) )
return 2*func(n-1);
}
Aber was ist damit?
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);
}
Bei zum Beispiel func (5) wird es zuerst wie folgt ausgeführt
5 -> 4 -> 3 -> 2 -> 1
Dann kehrt es zu 2 zurück, aber dort wird der "zweite" Teil ausgeführt, so dass der ganze Prozess aussieht
5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.
Daher ändert sich die Komplexität drastisch von O(n) zu O(2^n)
Lasst uns einen praktischen Beispielcode ausprobieren:
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);
}
}
Diese Ausgabe haben:
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
Aber wenn Sie sich an bereits berechnete Ergebnisse erinnern, ist die Komplexität immer noch O(n) sogar mit dem zweiten Ansatz:
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];
}
}
Diese Ausgabe haben:
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 für die Antwort № 2
Es hängt von der Semantik Ihrer Programmier- / Algorithmussprache ab.
Wenn durch f(n) Du meinst "Ruf die Funktion an, egal ob sie warmit dem gleichen Argument vorher aufgerufen "(wie es bei den meisten Programmiersprachen der Fall ist), dann reduziert Ihre Änderung die Komplexität dramatisch auf O (n). Sie haben einen O (1) Funktionsaufruf pro Dekrement des Arguments.
Sonst (wenn Sie über reine Funktionen sprechen und bekannte Ergebnisse bekannt machen), haben beide Algorithmen bereits die Komplexität O (n).