Die Laufzeitkomplexität einer "while" -Sloop hängt ganz davon ab, wie oft die Schleife iteriert. Es gibt keine einzige, endgültige Antwort. Es ist entscheidend, den Zustand zu analysieren, der die Schleife steuert und wie sich die an dieser Bedingung beteiligten Variablen innerhalb der Schleife ändern.

Hier ist eine Aufschlüsselung gemeinsamer Szenarien und ihrer Laufzeitkomplexität:

1. Konstante Zeit (o (1))

* Wenn die Schleife unabhängig von der Eingangsgröße eine feste, geringe Häufigkeit ausführt. Dies ist selten, aber es könnte passieren, wenn die Schleifenbedingung von einem konstanten Wert abhängt und nicht von der Eingabe beeinflusst wird.

`` `Python

I =0

Während ich <5:# Loops genau 5 Mal schleifen

drucken (i)

i +=1

`` `

2. Logarithmische Zeit (o (log n))

* Wenn die Schleife die Problemgröße durch einen konstanten Faktor in jeder Iteration reduziert. Ein klassisches Beispiel ist eine binäre Suche.

`` `Python

niedrig =0

hoch =n - 1

während niedrig <=hoch:# Loop dauert an, solange der Suchraum existiert

Mid =(niedrig + hoch) // 2

Wenn arr [Mid] niedrig =mid + 1

Elif arr [Mid]> Ziel:

hoch =Mitte - 1

anders:

Mitte # Target gefunden gefunden!

`` `

Hier ist die Größe des Suchraums (von "niedrig" bis `hoch") in jeder Iteration grob halbiert. Daher läuft die Schleife ungefähr `log2 (n)` Zeiten.

3. Lineare Zeit (o (n))

* Wenn die Schleife jedes Element eines Eingangs der Größe `n` einmal durchläuft. Das ist sehr häufig.

`` `Python

I =0

Während ich Druck (arr [i]) # Zugriff auf jedes Element von 'arr' einmal.

i +=1

`` `

In diesem Fall führt der Körper der Schleife "n' -Zeiten aus.

4. Quadratische Zeit (o (n^2))

* Wenn die Schleife für jedes von Elementen (oft verschachtelte Schleifen) iteriert.

`` `Python

I =0

Während ich J =0

Während J drucken (i, j)

J +=1

i +=1

`` `

Dies beinhaltet eine verschachtelte Schleife, in der beide Schleifen die Zeiten iterieren. Die Gesamtzahl der Iterationen ist `n * n =n^2`.

5. Andere Polynomzeit (o (n^k))

* Verallgemeinerungen des obigen quadratischen Beispiels. Zum Beispiel würden drei verschachtelte Schleifen, die jede Zeiten itererieren, zu einer Komplexität von O (n^3) führen.

6. Exponentialzeit (o (2^n)) oder schlechter

* Die Ausführungszeit der Schleife wächst exponentiell mit der Eingangsgröße. Dies weist häufig auf einen schlecht gestalteten Algorithmus oder ein Problem hin, das von Natur aus sehr schwierig ist. Beispiele könnten alle möglichen Kombinationen von Elementen aus versuchen.

wichtige Überlegungen:

* Eingangsgröße (n): Was repräsentiert "n"? Die Größe eines Arrays, die Größe einer Zahl usw. Dies ist entscheidend, um die Komplexität in Bezug auf die Eingabe auszudrücken.

* Bedingungsvariable Änderungen: Wie ändert sich die Variable (en), die die Schleifenbedingung in der Schleife steuert? Steigt es um eine konstante Menge, nimmt um einen Faktor ab usw.?

* Operationen innerhalb der Schleife: Die Laufzeit der Operationen * Inside * Die Schleife ist wichtig. Wenn Sie beispielsweise eine O (n) -Operation in einer Schleife haben, die n -mal ausgeführt wird, ist die Gesamtkomplexität o (n * n) =o (n^2).

So bestimmen Sie die Laufzeitkomplexität:

1. Identifizieren Sie die Eingangsgröße (n): Was ist der relevante Größenparameter?

2. Bestimmen Sie die Anzahl der Iterationen: Wie oft führt die Schleife in Bezug auf `n` *aus? Dies ist der Kernteil.

3. Betrachten Sie Operationen innerhalb der Schleife: Wenn die Schleife komplexe Operationen enthält, muss ihre Laufzeitkomplexität berücksichtigt werden. Die Gesamtkomplexität wird zur Komplexität der Schleifen -Iterationen multipliziert mit der Komplexität des teuersten Betriebs innerhalb der Schleife.

4. die Komplexität ausdrücken: Verwenden Sie eine große O -Notation (O (), ω (), θ ()), um die Obergrenze, die untere Grenze oder die enge Grenze der Laufzeit darzustellen. Normalerweise konzentrieren wir uns auf Big O (Worst-Case-Szenario).

Beispiel:

`` `Python

Def process_array (arr):

n =len (arr)

I =0

Während ich J =i + 1

während J Wenn arr [i]> arr [j]:

arr [i], arr [j] =arr [j], arr [i] # Konstante Zeitstausch

J +=1

i +=1

return arr

`` `

Analyse:

* `n` ist die Länge des Eingangsarray arr`.

* Die äußere Schleife (`I''''S) läuft" n' -Zeiten ".

* Die innere Schleife (`J`) läuft ungefähr` n - ich. Im schlimmsten Fall läuft es in der Zeit, wenn `Ich bin 0, Zeiten.

* Die Swap -Operation in der inneren Schleife ist o (1).

Daher tragen die verschachtelten Schleifen zur Komplexität von O (n^2) bei. Der Swap ist eine konstante Zeit und wirkt sich nicht auf die Laufzeit von O (n^2) aus. Dieser Algorithmus ähnelt der Auswahlsorten.

Zusammenfassend analysieren Sie sorgfältig, wie oft die Schleife relativ zur Eingabemaßgröße ausgeführt wird, um die Laufzeitkomplexität einer "while" -Schloop zu bestimmen, und berücksichtigen Sie die Komplexität der in der Schleife durchgeführten Operationen.