Warum werden verschachtelte Schleifen als schlechte Praxis angesehen?

33

Mein Vortragender erwähnte heute, dass es möglich sei, Schleifen in Java "zu beschriften", damit Sie sich beim Umgang mit verschachtelten Schleifen auf sie beziehen können. Also habe ich das Feature nachgeschlagen, da ich nichts davon wusste, und an vielen Stellen, an denen dieses Feature erklärt wurde, wurde es von einer Warnung gefolgt, die verschachtelte Schleifen abschreckt.

Ich verstehe nicht wirklich warum? Liegt es daran, dass es die Lesbarkeit des Codes beeinträchtigt? Oder ist es etwas "Technischeres"?

DSF
quelle
4
Wenn ich mich richtig an meinen CS3-Kurs erinnere, führt dies häufig zu einer exponentiellen Zeit, was bedeutet, dass Ihre Anwendung unbrauchbar wird, wenn Sie einen großen Datensatz erhalten.
Travis Pessetto
21
Eine Sache, die Sie über CS-Dozenten lernen sollten, ist, dass nicht alles, was sie sagen, zu 100% in der realen Welt gilt. Ich würde von mehr als ein paar tief verschachtelten Schleifen abraten, aber wenn Sie m x n Elemente verarbeiten müssen, um Ihr Problem zu lösen, werden Sie so viele Iterationen durchführen.
Blrfl
8
@TravisPessetto Tatsächlich ist es immer noch polynomielle Komplexität - O (n ^ k), wobei k die Anzahl der verschachtelten, nicht exponentiellen O (k ^ n) ist, wobei k eine Konstante ist.
m3th0dman
1
@ m3th0dman Danke, dass du mich korrigiert hast. Mein Lehrer war in diesem Fach nicht der Größte. Er behandelte O (n ^ 2) und O (k ^ n) als gleich.
Travis Pessetto
2
Verschachtelte Schleifen erhöhen die zyklomatische Komplexität (siehe hier ), was nach Ansicht einiger Leute die Wartbarkeit eines Programms verringert.
Marco

Antworten:

62

Verschachtelte Schleifen sind in Ordnung, solange sie den richtigen Algorithmus beschreiben.

Verschachtelte Schleifen haben Leistungsaspekte (siehe Antwort von @ Travis-Pesetto), aber manchmal ist es genau der richtige Algorithmus, z. B. wenn Sie auf jeden Wert in einer Matrix zugreifen müssen.

Das Beschriften von Schleifen in Java ermöglicht das vorzeitige Aufbrechen mehrerer verschachtelter Schleifen, wenn dies auf andere Weise umständlich wäre. Zum Beispiel könnte ein Spiel einen Code wie diesen haben:

Player chosen_one = null;
...
outer: // this is a label
for (Player player : party.getPlayers()) {
  for (Cell cell : player.getVisibleMapCells()) {
    for (Item artefact : cell.getItemsOnTheFloor())
      if (artefact == HOLY_GRAIL) {
        chosen_one = player;
        break outer; // everyone stop looking, we found it
      }
  }
}

Während Code wie im obigen Beispiel manchmal der optimale Weg ist, um einen bestimmten Algorithmus auszudrücken, ist es normalerweise besser, diesen Code in kleinere Funktionen zu unterteilen und wahrscheinlich returnanstelle von zu verwenden break. So ein breakmit einem Etikett ist ein schwacher Code Geruch ; Achten Sie besonders darauf, wenn Sie es sehen.

9000
quelle
2
Wie eine Randnotiz verwenden Grafiken einen Algorithmus, der auf jedes Teil einer Matrix zugreifen muss. Die GPU ist jedoch darauf spezialisiert, dies zeiteffizient zu handhaben.
Travis Pessetto
Ja, die GPU macht das massiv parallel. Die Frage handelte wohl von einem einzigen Hinrichtungsthread.
9000
2
Einer der Gründe, warum Etiketten eher verdächtig sind, ist, dass es oft eine Alternative gibt. In diesem Fall könnten Sie stattdessen zurückkehren.
jgmjgm
22

Verschachtelte Schleifen sind häufig (aber nicht immer) eine schlechte Übung, da sie häufig (aber nicht immer) zu viel für das sind, was Sie tun möchten. In vielen Fällen gibt es einen viel schnelleren und weniger verschwenderischen Weg, um das Ziel zu erreichen, das Sie erreichen möchten.

Wenn Sie beispielsweise 100 Elemente in Liste A und 100 Elemente in Liste B haben und wissen, dass für jedes Element in Liste A ein Element in Liste B übereinstimmt (wobei die Definition von "Übereinstimmung" absichtlich unklar bleibt) hier) und Sie möchten eine Liste von Paaren erstellen.

for each item X in list A:
  for each item Y in list B:
    if X matches Y then
      add (X, Y) to results
      break

Bei 100 Einträgen in jeder Liste sind durchschnittlich 100 * 100/2 (5.000) matchesVorgänge erforderlich. Bei mehr Artikeln oder wenn die 1: 1-Korrelation nicht gewährleistet ist, wird sie noch teurer.

Auf der anderen Seite gibt es eine viel schnellere Möglichkeit, eine Operation wie die folgende auszuführen:

sort list A
sort list B (according to the same sort order)
I = 0
J = 0
repeat
  X = A[I]
  Y = B[J]
  if X matches Y then
    add (X, Y) to results
    increment I
    increment J
  else if X < Y then
    increment I
  else increment J
until either index reaches the end of its list

Wenn Sie dies auf diese Weise tun matches, basiert die Anzahl der Vorgänge length(A) * length(B)nun auf length(A) + length(B), was bedeutet, dass Ihr Code viel schneller ausgeführt wird.

Mason Wheeler
quelle
10
Mit dem Vorbehalt, dass die Sortierung O(n log n)bei der Verwendung von Quicksort zweimal nicht unerheblich viel Zeit in Anspruch nimmt.
Robert Harvey
@ Robert Harvey: Natürlich. Aber das ist immer noch viel weniger als O(n^2)für nicht winzige Werte von N.
Mason Wheeler
10
Die zweite Version des Algorithmus ist im Allgemeinen falsch. Erstens wird angenommen, dass X und Y über den <Operator vergleichbar sind, was im Allgemeinen nicht vom matchesOperator abgeleitet werden kann. Zweitens kann der 2. Algorithmus auch dann noch falsche Ergebnisse liefern, wenn sowohl X als auch Y numerisch X matches Ysind X + Y == 100.
Pasha
9
@ user958624: Dies ist offensichtlich eine sehr allgemeine Übersicht über einen allgemeinen Algorithmus. Wie der Operator "Übereinstimmungen" muss das "<" so definiert werden, dass es im Kontext der zu vergleichenden Daten korrekt ist. Wenn dies korrekt durchgeführt wird, sind die Ergebnisse korrekt.
Mason Wheeler
PHP hat so etwas letztes gemacht, mit einem Array, das meiner Meinung nach einzigartig ist und / oder dem Gegenteil davon. Die Leute würden stattdessen nur die auf Hash basierenden PHP-Arrays verwenden und es wäre viel schneller.
jgmjgm
11

Ein Grund, Schleifen nicht zu verschachteln, ist, dass es eine schlechte Idee ist, Blockstrukturen zu tief zu verschachteln, unabhängig davon, ob sie Schleifen sind oder nicht.

Jede Funktion oder Methode sollte leicht verständlich sein, sowohl für den Zweck (der Name sollte ausdrücken, was sie tut) als auch für die Betreuer (die Interna sollten leicht verständlich sein). Wenn eine Funktion zu kompliziert ist, um sie leicht zu verstehen, bedeutet dies normalerweise, dass einige der Interna in separate Funktionen zerlegt werden sollten, damit sie in der (jetzt kleineren) Hauptfunktion namentlich erwähnt werden können.

Verschachtelte Schleifen können relativ schnell schwer zu verstehen sein, obwohl einige Verschachtelungen von Schleifen in Ordnung sind - vorausgesetzt, andere weisen darauf hin, dass Sie kein Leistungsproblem mit einem extrem (und unnötig) langsamen Algorithmus erstellen.

Tatsächlich brauchen Sie keine verschachtelten Schleifen, um absurd langsame Leistungsgrenzen zu erreichen. Stellen Sie sich zum Beispiel eine einzelne Schleife vor, die in jeder Iteration ein Element aus einer Warteschlange entnimmt und dann möglicherweise mehrere zurücksetzt - z. B. die Suche nach der Breite zuerst in einem Labyrinth. Die Leistung wird nicht durch die Verschachtelungstiefe der Schleife (die nur 1 beträgt) bestimmt, sondern durch die Anzahl der Elemente, die in diese Warteschlange gestellt werden, bevor sie schließlich erschöpft ist ( falls sie jemals erschöpft ist) - wie groß der erreichbare Teil der Schleife ist Labyrinth ist.

Steve314
quelle
1
Sie können eine verschachtelte Schleife sehr oft einfach reduzieren und es dauert immer noch dieselbe Zeit. Nehmen Sie für 0 bis Breite, für 0 bis Höhe; Sie können stattdessen einfach 0 für Breite und Höhe eingeben.
jgmjgm
@jgmjgm - Ja, es besteht die Gefahr, dass der Code in der Schleife kompliziert wird. Die Reduzierung kann dies zuweilen vereinfachen, aber häufiger erhöhen Sie die Komplexität der Wiederherstellung der tatsächlich gewünschten Indizes. Ein Trick dafür ist die Verwendung eines Indextyps, der die gesamte in der Logik verschachtelte Schleife zum Inkrementieren eines speziellen zusammengesetzten Index berücksichtigt - dies wird wahrscheinlich nicht nur für eine Schleife durchgeführt, aber möglicherweise gibt es mehrere Schleifen mit ähnlichen Strukturen oder möglicherweise Sie können eine flexiblere generische Version schreiben. Gemeinkosten für die Verwendung dieses Typs (falls vorhanden) können sich aus Gründen der Klarheit lohnen.
Steve314
Ich empfehle es nicht als eine gute Sache, aber wie überraschend einfach es sein kann, zwei Schleifen in eine zu verwandeln, ohne die zeitliche Komplexität zu beeinträchtigen.
jgmjgm
7

Bei vielen verschachtelten Schleifen erhalten Sie eine polynomielle Zeit. Zum Beispiel mit diesem Pseudocode:

set i equal to 1
while i is not equal to 100
  increment i
  set j equal to 1
  while j is not equal to i
    increment j
  end
 end

Dies würde als O (n ^ 2) -Zeit betrachtet, was eine Grafik ähnlich der folgenden sein würde: Bildbeschreibung hier eingeben

Wobei die y-Achse die Zeit ist, die Ihr Programm zum Beenden benötigt, und die x-Achse die Datenmenge ist.

Wenn Sie zu viele Daten erhalten, wird Ihr Programm so langsam sein, dass niemand darauf warten kann. und es sind nicht so viel wie 1000 Dateneinträge, von denen ich glaube, dass sie zu lange dauern werden.

Travis Pessetto
quelle
10
Vielleicht möchten Sie Ihren Graphen erneut auswählen: Das ist eine Exponentialkurve, keine quadratische, und durch Rekursion wird nichts aus O (n log n) von O (n ^ 2)
Ratschenfreak
5
Für die Rekursion habe ich zwei Wörter "Stapel" und "Überlauf"
Mateusz
10
Ihre Aussage, dass eine Rekursion eine O (n ^ 2) -Operation auf ein O (n log n) reduzieren kann, ist weitgehend ungenau. Derselbe Algorithmus, der rekursiv oder iterativ implementiert wird, sollte exakt dieselbe Komplexität der Big-O-Zeit aufweisen. Darüber hinaus kann die Rekursion häufig langsamer sein (abhängig von der Sprachimplementierung), da für jeden rekursiven Aufruf ein neuer Stapelrahmen erstellt werden muss, während für die Iteration nur eine Verzweigung / ein Vergleich erforderlich ist. Funktionsaufrufe sind normalerweise billig, aber nicht kostenlos.
Dckrooney
2
@TravisPessetto Ich habe in den letzten 6 Monaten 3 Stapelüberläufe festgestellt, als ich C # -Anwendungen aufgrund von rekursiven oder zyklischen Objektreferenzen entwickelte. Was ist daran komisch, dass es abstürzt und Sie nicht wissen, was Sie getroffen hat. Wenn Sie verschachtelte Schleifen sehen, wissen Sie, dass etwas Schlimmes passieren kann, und die Ausnahme über einen falschen Index für etwas ist leicht sichtbar.
Mateusz
2
@Mateusz auch Sprachen wie Java ermöglichen es Ihnen, einen Stapelüberlauffehler abzufangen. Dies mit einem Stack-Trace sollte Ihnen zeigen, was passiert ist. Ich habe nicht viel Erfahrung, aber das einzige Mal, dass ich einen Stapelüberlauffehler gesehen habe, ist in einem PHP, das einen Fehler hatte, der eine unendliche Rekursion verursachte, und dem PHP die 512 MB Speicher, die ihm zugewiesen wurden, ausgegangen sind. Die Rekursion muss einen endgültigen Endwert haben, der für Endlosschleifen nicht geeignet ist. Wie alles in CS gibt es eine Zeit und einen Ort für alle Dinge.
Travis Pessetto
0

Das Fahren eines 30-Tonnen-Lastwagens anstelle eines kleinen Personenkraftwagens ist eine schlechte Praxis. Außer wenn Sie 20 oder 30 Tonnen Zeug transportieren müssen.

Wenn Sie eine verschachtelte Schleife verwenden, ist dies keine schlechte Übung. Entweder ist es total dumm, oder es ist genau das, was benötigt wird. Du entscheidest.

Jemand beschwerte sich jedoch über das Beschriften von Schleifen. Die Antwort darauf: Wenn Sie die Frage stellen müssen, verwenden Sie keine Beschriftung. Wenn Sie genug wissen, um selbst zu entscheiden, dann entscheiden Sie selbst.

gnasher729
quelle
Wenn Sie genug wissen, um selbst zu entscheiden, wissen Sie genug, um keine markierten Schleifen zu verwenden. :-)
user949300
Nein. Wenn Ihnen genug beigebracht wurde, wurde Ihnen beigebracht, die gekennzeichnete Verwendung nicht zu verwenden. Wenn Sie genug wissen, gehen Sie über das Dogma hinaus und tun, was richtig ist.
gnasher729
1
Das Problem mit dem Etikett ist, dass es selten benötigt wird und viele Leute es frühzeitig einsetzen, um Fehler bei der Flusskontrolle zu umgehen. So ähnlich wie die Leute den Ausgang überall platzieren, wenn sie eine falsche Flusskontrolle haben. Funktionen machen es auch weitgehend überflüssig.
jgmjgm
-1

An verschachtelten Schleifen ist nichts von Natur aus falsch oder sogar schlecht. Sie haben jedoch bestimmte Überlegungen und Fallstricke.

Die Artikel, zu denen Sie geführt wurden, wahrscheinlich im Namen der Kürze oder aufgrund eines psychologischen Prozesses, der als verbrannt bezeichnet wird, wobei die Einzelheiten übersprungen wurden.

Verbrannt zu werden ist, wenn Sie eine negative Erfahrung mit dem impliziten Wesen haben, dann meiden Sie es. Zum Beispiel könnte ich Gemüse mit einem scharfen Messer schneiden und mich selbst schneiden. Ich könnte dann sagen, scharfe Messer sind schlecht. Verwenden Sie sie nicht, um Gemüse zu schneiden, um zu versuchen, zu verhindern, dass diese schlechte Erfahrung jemals wieder vorkommt. Das ist natürlich sehr unpraktisch. In Wirklichkeit muss man nur vorsichtig sein. Wenn Sie jemand anderem sagen, dass er Gemüse schneiden soll, haben Sie ein noch stärkeres Gefühl dafür. Wenn ich Kinder anweisen würde, Gemüse zu schneiden, würde ich sie nachdrücklich auffordern, kein scharfes Messer zu verwenden, besonders wenn ich sie nicht genau überwachen kann.

Das Problem bei der Programmierung ist, dass Sie nicht die maximale Effizienz erreichen, wenn Sie immer zuerst Sicherheit bevorzugen. In diesem Fall können die Kinder nur weiches Gemüse schneiden. Konfrontiert mit irgendetwas anderem und sie werden es nur mit einem stumpfen Messer durcheinander bringen. Es ist wichtig, die richtige Verwendung von Schleifen, einschließlich verschachtelter Schleifen, zu erlernen. Dies ist nicht möglich, wenn sie als schlecht eingestuft werden und Sie niemals versuchen, sie zu verwenden.

Wie viele Antworten hier darauf hinweisen, ist eine verschachtelte for-Schleife ein Hinweis auf die Leistungsmerkmale Ihres Programms, die sich bei jeder Verschachtelung exponentiell verschlechtern können. Das heißt, O (n), O (n ^ 2), O (n ^ 3) usw., die O (n ^ depth) umfassen, wobei depth angibt, wie viele Schleifen Sie verschachtelt haben. Wenn Ihre Verschachtelung zunimmt, nimmt die erforderliche Zeit exponentiell zu. Das Problem dabei ist, dass es weder eine Gewissheit dafür ist, dass Ihre zeitliche oder räumliche Komplexität so ist (ziemlich oft laufen a * b * c, aber möglicherweise werden nicht alle Nest-Schleifen die ganze Zeit ausgeführt), noch eine Gewissheit dafür, dass Sie dies tun habe ein Leistungsproblem, auch wenn es das ist.

Für viele Menschen, insbesondere für Studenten, Schriftsteller und Dozenten, die, um ehrlich zu sein, selten ihren Lebensunterhalt verdienen oder tagtäglich Schleifen programmieren, ist dies möglicherweise auch etwas, an das sie nicht gewöhnt sind, und das zu viel kognitive Belastung für frühe Begegnungen verursacht hat. Dies ist ein problematischer Aspekt, da es immer eine Lernkurve gibt, und wenn Sie vermeiden, dass Studenten zu Programmierern werden, ist dies nicht effektiv.

Verschachtelte Schleifen können wild werden, das heißt, sie können sehr tief verschachtelt enden. Wenn ich durch jeden Kontinent gehe, dann durch jedes Land, dann durch jede Stadt, dann durch jedes Geschäft, dann durch jedes Regal, dann durch jedes Produkt, wenn es eine Dose Bohnen durch jede Bohne ist, und messe ihre Größe, um den Durchschnitt zu erhalten, dann du kann sehen, dass sehr tief nisten wird. Sie haben eine Pyramide und viel verschwendeten Platz am linken Rand. Sie könnten sogar die Seite verlassen.

Dies ist ein Problem, das historisch bedeutender wäre, wenn Bildschirme klein und von geringer Auflösung wären. In diesen Fällen könnten sogar einige Verschachtelungsebenen wirklich viel Platz beanspruchen. Dies ist heutzutage ein geringeres Problem, da der Schwellenwert höher ist, obwohl dies bei ausreichender Verschachtelung immer noch ein Problem darstellen kann.

Verwandt ist das ästhetische Argument. Viele Menschen finden verschachtelte Schleifen nicht ästhetisch ansprechend im Gegensatz zu Layouts mit einer konsistenteren Ausrichtung. Dies kann mit dem, woran Menschen gewöhnt sind, der Blickverfolgung und anderen Belangen zusammenhängen oder nicht. Es ist jedoch insofern problematisch, als es dazu neigt, sich selbst zu verstärken und das Lesen von Code letztendlich zu erschweren, da ein Codeblock aufgelöst und Schleifen hinter Abstraktionen, wie z. B. Funktionen, eingekapselt werden.

Es gibt eine natürliche Tendenz zu dem, was die Menschen gewohnt sind. Wenn Sie etwas auf einfachste Weise programmieren, ist die Wahrscheinlichkeit, dass keine Verschachtelung erforderlich ist, am höchsten. Die Wahrscheinlichkeit, dass eine Ebene erforderlich ist, sinkt um eine Größenordnung. Die Wahrscheinlichkeit, dass eine andere Ebene erforderlich ist, sinkt erneut. Die Frequenz sinkt und bedeutet im Wesentlichen, je tiefer die Verschachtelung ist, desto weniger trainiert sind die menschlichen Sinne, um dies zu antizipieren.

Dies hängt damit zusammen, dass in jedem komplexen Konstrukt, für das eine verschachtelte Schleife in Betracht gezogen werden kann, immer die einfachste mögliche Lösung gefragt werden muss, da möglicherweise eine fehlende Lösung weniger Schleifen benötigt. Die Ironie ist, dass eine verschachtelte Lösung oft die einfachste Möglichkeit ist, etwas zu produzieren, das mit minimalem Aufwand, Komplexität und kognitiver Belastung funktioniert. Es ist oft natürlich, nach Schleifen zu nisten. Betrachten Sie zum Beispiel eine der obigen Antworten, bei denen der viel schnellere Weg als bei einer verschachtelten for-Schleife auch weitaus komplexer ist und aus erheblich mehr Code besteht.

Es ist viel Sorgfalt erforderlich, da es häufig möglich ist, Schleifen zu beseitigen oder zu reduzieren, wobei das Endergebnis letztendlich eine Heilung ist, die schlechter als die Krankheit ist, insbesondere wenn Sie beispielsweise keine messbare und signifikante Leistungsverbesserung durch die Anstrengung erhalten.

Es kommt sehr häufig vor, dass es im Zusammenhang mit Schleifen zu Leistungsproblemen kommt, die den Computer anweisen, eine Aktion viele Male zu wiederholen, und die von Natur aus häufig in Leistungsengpässe verwickelt sind. Leider können Antworten darauf sehr oberflächlich sein. Es ist üblich, dass Menschen eine Schleife sehen und ein Leistungsproblem sehen, bei dem es keine gibt, und dann die Schleife vor dem Sehen verbergen, um keine wirklichen Auswirkungen zu haben. Der Code "sieht" schnell aus, aber stellen Sie ihn auf die Straße, geben Sie die Zündung ein, betätigen Sie das Gaspedal und sehen Sie sich den Tacho an. Vielleicht ist er immer noch so schnell wie eine alte Dame, die ihren Zimmer-Rahmen betritt.

Diese Art des Versteckens ist ähnlich wie wenn Sie zehn Muggers auf Ihrer Route haben. Wenn Sie keinen geraden Weg zu Ihrem Ziel haben, sondern hinter jeder Ecke einen Räuber anordnen, entsteht die Illusion, dass es auf Ihrer Reise keine Räuber gibt. Aus dem Auge, aus dem Sinn. Du wirst immer noch zehnmal überfallen, aber jetzt wirst du es nicht kommen sehen.

Die Antwort auf Ihre Frage ist, dass es beides ist, aber keine der Bedenken ist absolut. Sie sind entweder ganz subjektiv oder nur kontextuell objektiv. Leider hat manchmal die ganz subjektive oder eher Meinung Vorrang und dominiert.

Als Faustregel gilt, wenn eine verschachtelte Schleife benötigt wird oder dies als nächster offensichtlicher Schritt erscheint, ist es am besten, nicht zu überlegen und dies einfach zu tun. Wenn jedoch Zweifel bestehen, sollte dies später überprüft werden.

Eine andere Faustregel ist, dass Sie immer die Kardinalität überprüfen und sich fragen sollten, ob diese Schleife ein Problem sein wird. In meinem vorherigen Beispiel bin ich durch Städte gegangen. Zum Testen gehe ich vielleicht nur durch zehn Städte, aber was ist eine vernünftige maximale Anzahl von Städten, die in der realen Welt zu erwarten sind? Ich könnte das dann für Kontinente mit demselben multiplizieren. Es ist eine Faustregel, bei Schleifen immer zu berücksichtigen, dass eine dynamische (variable) Anzahl von Malen durchlaufen wird, die sich später möglicherweise ergeben.

Egal was immer zuerst funktioniert. Wenn Sie eine Möglichkeit zur Optimierung sehen, können Sie Ihre optimierte Lösung mit der einfachsten vergleichen und bestätigen, dass die erwarteten Vorteile erzielt wurden. Sie können auch zu lange vorzeitig optimieren, bevor die Messungen durchgeführt werden. Dies führt zu YAGNI oder zu viel Zeitverschwendung und Terminüberschreitungen.

jgmjgm
quelle
Das scharfe <-> stumpfe Messer Beispiel ist nicht groß, als stumpfes Messer ist im Allgemeinen mehr zum Schneiden gefährlich. Und O (n) -> O (n ^ 2) -> O (n ^ 3) nicht exponentiell in n, ist es geometrisch oder Polynom .
Caleth
Dass stumpfe Messer schlimmer sind, ist ein urbaner Mythos. In der Praxis variiert sie und ist normalerweise spezifisch für den Fall, dass stumpfe Messer besonders ungeeignet sind und normalerweise viel Kraft erfordern und viel Schlupf verursachen. Sie haben Recht, es gibt eine versteckte, aber inhärente Einschränkung, Sie können nur weiches Gemüse schneiden. Ich würde n ^ tiefe Exponential betrachten, aber Sie haben Recht, diese Beispiele allein sind es nicht.
jgmjgm
@jgmjgm: n ^ Tiefe ist Polynom, Tiefe ^ n ist Exponential. Es ist nicht wirklich eine Frage der Interpretation.
Roel Schroeven
x ^ y unterscheidet sich von y ^ x? Der Fehler, den Sie gemacht haben, ist, dass Sie die Antwort nie nicht gelesen haben. Sie haben für exponentielle und dann für Gleichungen, die für sich genommen nicht exponentiell sind, gegriffen. Wenn Sie lesen, werden Sie sehen, dass ich sagte, dass es für jede Verschachtelungsebene exponentiell ansteigt, und wenn Sie das selbst testen, Zeit für (a = 0; a <n; a ++); für (b = 0; b <n ; b ++); für (c = 0; c <n; c ++); Wenn Sie Schleifen hinzufügen oder entfernen, werden Sie feststellen, dass dies tatsächlich exponentiell ist. Sie werden feststellen, dass eine Schleife bei n ^ 1 ausgeführt wird, zwei bei n ^ 2 und drei bei n ^ 3. Sie verstehen verschachtelt nicht: D. Gemoetrische Teilmengen exponentiell.
jgmjgm
Ich denke, das beweist, dass die Leute wirklich mit verschachtelten Konstrukten zu kämpfen haben.
jgmjgm