Mit dieser Funktion kann die Laufzeit
Hallo, ich habe diese Frage nicht analysieren, aber ich habe falsch und ich das einfach nicht verstehen. Es geht darum, die exakte Laufzeit dieser verschachtelten Schleife zu erhalten.
Konkret kann ich bis "für i = 2, innere Schleife Laufzeit: 2n-2" verstehen. Aber danach kann ich es nicht verstehen.
Frage 1)
Zuerst sagt er For i=n, inner loop runtime is n+1
. Aber das ergibt aus meiner Sicht keinen Sinn. Nehmen wir an, n = 3 und die äußere Schleife führt ihre letzte Schleife aus, wenn i = 3, dann wird j die innere Schleife dreimal durchlaufen (von 3 bis 5, da j = 3 = n < 2 * n = 2 * 3 = 6). Antwort sagt aber inner loop runtime is n+1
, wenn ich 3 in n+1
stelle, wird es 4 Mal. Ich verstehe nicht, warum diese Antwort richtig ist.
Frage 2)
Wie kann ich letzte Form der Antwort 1.5n^2 + 0.5n
von 2n+(2n-1)+(2n-2)+...+(n+1)
bekommen? Kannst du mir allgemeine Schritte zeigen, wie früher die letzteren in Mathematik wurden? Speziell darüber, wie 2n + (2n-1) + (2n-2) + ... + (n+1)
n*n + (1+2+3+...+n)
werden? Ich denke, Formel n(n+1)/2
wird hier mit n=(n+1)
verwendet, aber es funktioniert nicht für mich.
Wird hier irgendeine Formel verwendet?
das ist viel einfacher zu verstehen Wenn Sie die Anfangssumme als 'n + (n + 1) + (n + 2) + ... + (n + n) 'schreiben, sollte es ziemlich offensichtlich sein, wie Sie zum nächsten Schritt kommen. – Dukeling