Was ist die Komplexität der T(n)=1+2+3+...+n? Ich weiß, dass die Antwort O(n^2) ist. Was ist ein Beispiel für einen Algorithmus mit Laufzeit T(n)?Beispiel 1 + 2 + 3 + ... + n Summe Algorithmus
EDIT: ich nicht sprach die Summe der Berechnung 1 + 2 + 3 + ... + n, das ist nicht die objetive.
Die Reihenfolge der das Wachstum einer Funktion mit der Anzahl der Operationen, die Sie ausführen müssen, zu tun. Ein Beispiel für eine Funktion mit O (n) wäre die langsame Version der Funktion, die Sie in der Frage erwähnt haben. In Python:
total = 0
for i in range(n + 1):
total += i
Dies wäre O (n), da die Menge an Zeit auf n linear auf Basis skaliert abzuschließen es dauert.
Wie für die Funktion, die Sie als Beispiel in der Frage angegeben haben, ist es tatsächlich O (1), weil Sie nur eine Operation ausführen müssen: n(n+1)/2. Die Menge an Zeit in Anspruch nimmt es n(n+1)/2 nie bar ändern Back-End-Macken zu berechnen, aber für so etwas, das wirklich sollte nicht immer egal.
Die Frage war nicht, wie lange es dauert, die Summe zu berechnen, es ging darum, die Funktion T (n) asymptotisch als Groß-O auszudrücken. – interjay
Die Frage wurde bearbeitet. Es ging um alternative Beispiele für die (falsche) Annahme von O (n^2), um das Ergebnis zu berechnen. Das Ergebnis des angegebenen Beispiels kann mit O (1) berechnet werden, was eine echte und korrekte Alternative ist. O (n) ist trivial, wenn Sie das wirklich wollen: einfach Schleife und Summe. O (n^2) ist falsch, denn das ist nicht T (n) = 1 + (1 + 2) + (1 + 2 + 3) + ... + (1 + 2 +3 + ...+ n), aber jetzt argumentieren wir Semantik statt Mathematik, die bereits gelöst wurde. –
@SteveHarris Die Absicht der Frage war die gleiche vor und nach der Bearbeitung. T (n) ist kein Algorithmus, sondern die Laufzeit eines anderen Algorithmus. Die Frage fragt, welcher Algorithmus eine Laufzeit von T (n) hat. Und die Frage ist richtig, wenn wir sagen, dass T (n) in der Klasse von O (n^2) ist. – interjay
Was ist ein Beispiel für einen Algorithmus mit Laufzeit T (n)?
Wenn Sie eine äußere Schleife, die n Zeiten und eine innere Schleife iteriert, die i mal iteriert wo i der Index der äußeren Schleife ist, wird der Körper der inneren Schleife T(n) mal ausgeführt werden.
Ein Beispiel eines solchen verschachtelten Schleife der folgende Algorithmus wäre:
for i from 1 to n
for j from 1 to i
print "$j "
print "\n"
, die die Lösung auf einen gemeinsamen Hausaufgabe ist und druckt eine Anzahl pyramiden der folgenden Form:
1
1 2
1 2 3
Upvoted, aber es ist umstritten, ob "print" $ j "' O (1) ist, da es ~ log_10 (j) Zeichen ausgibt. Wenn Sie die Ausgabe von 1 Zeichen als Grundoperation zählen, ist das Beispiel O (n^2 log n). Wenn Sie die Druckanweisung als O (1) betrachten, egal was gedruckt wird, dann ist es O (n^2). –
@PaulHankin Ich denke, dass ich meinen Arsch in dieser Hinsicht bedeckt habe, indem ich behaupte, dass der Körper der inneren Schleife 'T (n)' mal ausgeführt wird (obwohl das zugegebenermaßen nicht ganz das war);) Sie können dieses Problem lösen indem Sie "*" anstelle von "$ j" drucken. Das könnte tatsächlich die häufigere Variante der Hausaufgabe sein. – sepp2k
Insertionsort im schlimmsten Fall erfordert T(n)=1+2+3+...+n begrenzte Zeitschritte. Auswahlsortierung erfordert jedes Mal viele Schritte, aber es ist nicht so häufig.
Während @ sepp2k eine wunderbare Antwort gibt, ist hier einige echte Leben Algorithmen, die T(N) = 1+2+3+...+n haben
Insertion Sort in seiner schlimmsten Fall (also wir einen solchen Algorithmus O(n^2) genannt): Es hat eine äußere Schleife, die Schleife n mal, und für die innere Schleife, Schleifen es den sortierten Teil des Arrays, um eine Position zum Einfügen des nächsten Elements zu finden, wo der sortierte Teil um 1 für jede äußere Schleife Iteration erhöht, so dass die innere Schleife im schlimmsten Fall 1+2+3+4+..+n-1 läuft mal
Longest Increasing Subsequence (LIS) naive implementation mit: Direkte Umsetzung der Rekursion , das für jede Iteration i, müssen wir durch all < i
Interval Graph Coloring (Interval Partitioning) mit naiver Implementierung j aussehen: Nach den Intervallen sortieren, für jedes Intervall x, müssen wir feststellen, wie viele Intervalle vor x im Konflikt mit x, und die Antwort auf das Problem ist die maximale Konfliktzahl. So, während die äußere Schleife jedes Intervall wird Looping i wird die innere Schleife für alle Test j < i
Prime Generating mit naiven primality Looping: Natürlich können wir alle Primzahlen innerhalb n, mit naiven Primzahltest auf allen i erzeugen innerhalb n. Das heißt, für alle i, wir Schleife für alle j < i zu sehen, ob j teilt i
Tatsächlich gibt es viele Algorithmen, die eine solche Struktur enthält, und die meisten von ihnen, dass ich gesehen haben, können durch die Verwendung eines verbessert werden brillanterer Algorithmus oder erweiterte Datenstruktur.
Das kann (n) in 'O erfolgen', Warum denkst du, es ist "O (n^2)"? –
Ich erinnere mich, dass ich dies einmal im Kalkül getan habe, diese Summe 1 + 2 + 3 + ... + n ist gleich n (n + 1)/2, und durch Multiplikation können wir sagen, dass es O (n^2). Bitte korrigieren Sie mich, falls ich falsch liege. – Kamoukou
'n (n + 1)/2' ist einfach eine Konstante, die' O (1) 'ist. Um hier klar zu sein, gilt 'n! = O (n)', das bezieht sich auf die tatsächliche Zahl 'n'. –