Hier volgt een overzicht van veelvoorkomende scenario's en hun runtime-complexiteit:

1. Constante tijd (O(1))

* Wanneer de lus een vast, klein aantal keren wordt uitgevoerd, ongeacht de invoergrootte. Dit komt zelden voor, maar kan gebeuren als de lusconditie afhankelijk is van een constante waarde en niet wordt beïnvloed door de invoer.

```python

ik =0

terwijl i <5:# Loopt precies 5 keer door

afdrukken(ik)

ik +=1

```

2. Logaritmische tijd (O(log n))

* Wanneer de lus de probleemgrootte in elke iteratie met een constante factor verkleint. Een klassiek voorbeeld is binair zoeken.

```python

laag =0

hoog =n - 1

while low <=high:# Loop gaat door zolang de zoekruimte bestaat

midden =(laag + hoog) // 2

if arr[mid] laag =midden + 1

elif arr[mid]> doel:

hoog =midden - 1

anders:

terugkeer midden # Doel gevonden!

```

Hier wordt de grootte van de zoekruimte (van 'laag' tot 'hoog') in elke iteratie grofweg gehalveerd. Daarom loopt de lus ongeveer 'log2(n)' keer.

3. Lineaire tijd (O(n))

* Wanneer de lus elk element van een invoer met grootte `n` één keer doorloopt. Dit is heel gebruikelijk.

```python

ik =0

while i print(arr[i]) # Eén keer toegang tot elk element van 'arr'.

ik +=1

```

In dit geval voert de body van de lus `n` keer uit.

4. Kwadratische tijd (O(n^2))

* Wanneer de lus `n` keer itereert voor elk van `n` elementen (vaak geneste lussen).

```python

ik =0

terwijl ik j =0

terwijl j afdrukken(i, j)

j+=1

ik +=1

```

Dit omvat een geneste 'while'-lus, waarbij beide lussen 'n' keer worden herhaald. Het totale aantal iteraties is `n * n =n^2`.

5. Andere polynomiale tijd (O(n^k))

* Generalisaties van het kwadratische voorbeeld hierboven. Drie geneste lussen die elk `n` keer itereren, zouden bijvoorbeeld resulteren in O(n^3) complexiteit.

6. Exponentiële tijd (O(2^n)) of erger

* De uitvoeringstijd van de lus groeit exponentieel met de invoergrootte. Dit duidt vaak op een slecht ontworpen algoritme of een probleem dat inherent erg moeilijk is. Voorbeelden hiervan zijn het uitproberen van alle mogelijke combinaties van elementen.

Belangrijke overwegingen:

* Invoergrootte (n): Wat betekent 'n'? De grootte van een array, de grootte van een getal, enz. Dit is van cruciaal belang om de complexiteit in termen van invoer uit te drukken.

* Wijzigingen in conditievariabelen: Hoe veranderen de variabelen die de lusvoorwaarde regelen binnen de lus? Neemt de waarde toe met een constant bedrag, neemt deze af met een factor, enz.?

* Bewerkingen binnen de lus: De looptijd van de bewerkingen *binnen* de lus is van belang. Als u bijvoorbeeld een O(n)-bewerking hebt binnen een lus die n keer wordt uitgevoerd, is de algehele complexiteit O(n * n) =O(n^2).

Hoe u de runtime-complexiteit kunt bepalen:

1. Identificeer de invoergrootte (n): Wat is de relevante maatparameter?

2. Bepaal het aantal iteraties: Hoe vaak wordt de lus *in relatie tot `n`* uitgevoerd? Dit is het kerngedeelte.

3. Overweeg operaties binnen de lus: Als de lus complexe bewerkingen bevat, moet rekening worden gehouden met de complexiteit ervan tijdens de looptijd. De algehele complexiteit wordt de complexiteit van de lusiteraties vermenigvuldigd met de complexiteit van de duurste bewerking binnen de lus.

4. Druk de complexiteit uit: Gebruik de Big O-notatie (O( ), Ω( ), Θ( )) om de bovengrens, ondergrens of strakke grens van de runtime weer te geven. Meestal concentreren we ons op Big O (worst case scenario).

Voorbeeld:

```python

def proces_array(arr):

n =len(arr)

ik =0

terwijl ik j =ik + 1

terwijl j als arr[i]> arr[j]:

arr[i], arr[j] =arr[j], arr[i] # Constante tijdwissel

j+=1

ik +=1

retour arr

```

Analyse:

* `n` is de lengte van de invoerarray `arr`.

* De buitenste lus (`i`) loopt `n` keer.

* De binnenste lus (`j`) loopt ongeveer `n - i` keer. In het ergste geval, wanneer `i` 0 is, wordt `n` keer uitgevoerd.

* De wisseloperatie binnen de binnenste lus is O(1).

Daarom dragen de geneste lussen bij aan de O(n^2)-complexiteit. De swap heeft een constante tijd en heeft geen invloed op de algehele O(n^2)-runtime. Dit algoritme is vergelijkbaar met selectiesortering.

Samenvattend:om de runtime-complexiteit van een 'while'-lus te bepalen, analyseert u zorgvuldig hoe vaak de lus wordt uitgevoerd in verhouding tot de invoergrootte en houdt u rekening met de complexiteit van de bewerkingen die binnen de lus worden uitgevoerd.