Tidskomplexiteten för ett "if" -uttalande är i allmänhet
o (1) , men med några viktiga varningar. Här är en uppdelning:
Kärnidén:konstant tid
* grenning är snabb: Den primära operationen i ett "if" -uttalande utvärderar villkoret och beslutar vilken gren som ska köras. Detta är en mycket snabb, deterministisk process som involverar en enda jämförelse (eller en serie booleska operationer som kan betraktas som begränsade). Moderna processorer är mycket optimerade för villkorad förgrening.
* Oberoende av ingångsstorlek: Beslutet att utföra blocket "if" eller "annars" -blocket (eller varken om det inte finns något "annat") beror inte på storleken på den ingångsdata som behandlas av den omgivande algoritmen. Det beror bara på själva tillståndet.
Varför O (1) kan vara vilseledande (sammanhangsfrågor!)
Medan "if" -uttalandet * själv * är o (1), kan * koden * inuti "if" -blocket eller "annars" -blocket ha någon tidskomplexitet. Detta är avgörande. Tänk på dessa scenarier:
1. o (1) if-block:
`` `python
Om x> 5:
y =10 # o (1) Uppdrag
z =x + y # o (1) Tillägg
annan:
y =20 # o (1) Uppdrag
`` `
I detta fall är uttalandet "if" och koden inom * båda * grenarna o (1). Den övergripande komplexiteten för detta utdrag är O (1).
2. o (n) if-block:
`` `python
om len (my_list)> 0:
för i inom räckvidd (len (my_list)):# o (n) slinga
tryck (my_list [i])
annan:
utskrift ("Listan är tom") # o (1)
`` `
Här, om villkoret är sant, kör du en slinga som itererar genom "my_list", vilket gör komplexiteten i "if" gren o (n). Om villkoret är falskt kör du O (1) kod. Det * värsta fallet * komplexiteten i hela kodblocket är o (n), eftersom uttalandet "if" kan leda till att utföra O (n) -koden.
3. o (n^2) if-block:
`` `python
Om villkor:
för jag inom räckvidden (n):
för J inom räckvidd (n):
# Vissa O (1) operation
passera
annan:
# O (1) Drift
passera
`` `
I det här exemplet blir tidskomplexiteten o (n^2) på grund av de kapslade slingorna inuti "om" -uttalandet, även om utvärderingen av "if" -villkoret fortfarande är o (1).
Sammanfattningsvis
* Uttalets förgreningslogik är o (1).
* Den övergripande tidskomplexiteten för koden som innehåller "if" -uttalandet beror helt på komplexiteten i koden * inuti * "if" och "annars" -blocken. Blocket med den högsta komplexiteten kommer att dominera.
* När du analyserar algoritmer måste du överväga det värsta fallet, som vanligtvis involverar "if" -blocket med den högsta komplexiteten som genomförs.
Därför, medan du kan säga att "if" * uttalandet i sig * tar ständig tid, måste du Analysera koden inuti grenarna för att bestämma den verkliga tidskomplexiteten för kodblocket som innehåller "if". Fokusera på den dominerande termen (kodblocket som tar längst att utföra när ingångsstorleken växer).
