Tidskompleksiteten af ​​en 'hvis' -opgørelse er generelt O (1) , men med nogle vigtige advarsler. Her er en sammenbrud:

Kerneideen:Konstant tid

* forgrening er hurtig: Den primære operation i en 'if' -klæring vurderer betingelsen og beslutter, hvilken gren der skal udføres. Dette er en meget hurtig, deterministisk proces, der involverer en enkelt sammenligning (eller en række boolske operationer, der kan betragtes som afgrænset). Moderne processorer er meget optimeret til betinget forgrening.

* uafhængigt af inputstørrelse: Beslutningen om at udføre "if" -blokken eller "andet" -blokken (eller hverken hvis der ikke er nogen "andet") afhænger ikke af størrelsen på de inputdata, der behandles af den omgivende algoritme. Det afhænger kun af selve tilstanden.

Hvorfor O (1) kan være vildledende (kontekst betyder noget!)

Mens selve "if" -opgørelsen * er o (1), kan * -koden * inde i "hvis" -blokken eller "andet" -blokken have enhver tidskompleksitet. Dette er afgørende. Overvej disse scenarier:

1. o (1) if-blok:

`` `Python

Hvis x> 5:

Y =10 # o (1) Opgave

z =x + y # o (1) tilføjelse

andet:

y =20 # o (1) Opgave

`` `

I dette tilfælde er "if" -opgørelsen og koden inden for * begge * grene O (1). Den samlede kompleksitet af dette uddrag er O (1).

2. o (n) if-blok:

`` `Python

Hvis len (my_list)> 0:

for jeg inden for rækkevidde (len (my_list)):# o (n) loop

print (my_list [i])

andet:

Udskriv ("Liste er tom") # o (1)

`` `

Her, hvis tilstanden er sand, udfører du en løkke, der itererer gennem 'my_list', hvilket gør kompleksiteten af ​​'if' gren o (n). Hvis betingelsen er falsk, udfører du O (1) -kode. Den * værste case * -kompleksitet i hele denne kodeblok er O (n), fordi `hvis '-opgørelsen kan føre til udførelse af O (n) -koden.

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

`` `Python

Hvis betingelsen:

for jeg inden for rækkevidde (n):

For J i rækkevidde (n):

# Nogle o (1) operation

passere

andet:

# O (1) Betjening

passere

`` `

I dette eksempel bliver tidskompleksiteten O (n^2) på grund af de indlejrede løkker inde i "if" -opgørelsen, selvom evalueringen af ​​"hvis" -tilstanden stadig er O (1).

Kortfattet

* "IF" -opgørelsens forgreningslogik er O (1).

* Den samlede tidskompleksitet af koden, der indeholder `if '-opgørelsen, afhænger helt af kompleksiteten af ​​koden * inde * i' hvis 'og' andet 'blokke. Blokken med den højeste kompleksitet vil dominere.

* Når du analyserer algoritmer, skal du overveje det værste tilfælde, som normalt involverer den 'hvis' blok med den højeste kompleksitet, der udføres.

Derfor, mens du kan sige 'hvis' * -opgørelsen * tager konstant tid, skal du Analyser koden inde i grenene for at bestemme den sande tidskompleksitet af kodeblokken, der indeholder `IF '. Fokuser på det dominerende udtryk (kodeblokken, der vil tage det længste at udføre, når inputstørrelsen vokser).