Het kernidee:constante tijd

* Vertakken gaat snel: De primaire bewerking in een `if`-instructie is het evalueren van de voorwaarde en het beslissen welke vertakking moet worden uitgevoerd. Dit is een zeer snel, deterministisch proces dat een enkele vergelijking omvat (of een reeks Booleaanse bewerkingen die als begrensd kunnen worden beschouwd). Moderne processors zijn sterk geoptimaliseerd voor voorwaardelijke vertakking.

* Onafhankelijk van de invoergrootte: De beslissing om het 'if'-blok of het 'else'-blok uit te voeren (of geen van beide als er geen 'else' is) hangt niet af van de grootte van de invoergegevens die door het omringende algoritme worden verwerkt. Het hangt alleen af ​​van de toestand zelf.

Waarom O(1) misleidend kan zijn (context is belangrijk!)

Terwijl de `if`-instructie *itself* O(1) is, kan de *code* binnen het `if`-blok of `else`-blok elke tijdscomplexiteit hebben. Dit is cruciaal. Overweeg deze scenario's:

1. O(1) if-blok:

```python

als x> 5:

y =10 # O(1) toewijzing

z =x + y # O(1) optelling

anders:

y =20 # O(1) toewijzing

```

In dit geval zijn de `if`-instructie en de code binnen *beide* takken O(1). De algehele complexiteit van dit fragment is O(1).

2. O(n) if-blok:

```python

als len(mijn_lijst)> 0:

for i binnen bereik(len(mijn_lijst)):# O(n) lus

print(mijn_lijst[i])

anders:

print("Lijst is leeg") # O(1)

```

Als de voorwaarde waar is, voer je hier een lus uit die door `my_list` loopt, waardoor de complexiteit van de `if`-tak O(n) wordt. Als de voorwaarde onwaar is, voert u O(1)-code uit. De *worst-case* complexiteit van dit hele codeblok is O(n), omdat de `if`-instructie zou kunnen leiden tot het uitvoeren van de O(n)-code.

3. O(n^2) if-blok:

```python

indien voorwaarde:

voor ik binnen bereik(n):

voor j binnen bereik(n):

# Een O(1)-bewerking

doorgang

anders:

# O(1)-bewerking

doorgang

```

In dit voorbeeld wordt de tijdscomplexiteit O(n^2) vanwege de geneste lussen binnen de `if`-instructie, ook al is de evaluatie van de `if`-voorwaarde nog steeds O(1).

Samenvatting

* De vertakkingslogica van de `if`-instructie is O(1).

* De algehele tijdscomplexiteit van de code die de `if`-instructie bevat, hangt volledig af van de complexiteit van de code *in* de `if`- en `else`-blokken. Het blok met de hoogste complexiteit zal domineren.

* Bij het analyseren van algoritmen moet je rekening houden met het worstcasescenario, waarbij meestal het 'if'-blok met de hoogste complexiteit wordt uitgevoerd.

Hoewel je dus kunt zeggen dat de `if` *instructie zelf* constante tijd kost, moet dat wel analyseer de code binnen de vertakkingen om de werkelijke tijdscomplexiteit te bepalen van het codeblok dat de 'if' bevat. Concentreer u op de dominante term (het codeblok dat het langst nodig heeft om uit te voeren naarmate de invoer groter wordt).