Aká je časová zložitosť vyhlásenia IF v programovacom jazyku?

Časová zložitosť vyhlásenia „if“ je všeobecne o (1) , ale s niektorými dôležitými upozorneniami. Tu je porucha:

Základná myšlienka:konštantný čas

* Vetvenie je rýchle: Primárnou operáciou vo vyhlásení „if“ je vyhodnotenie stavu a rozhodovanie o tom, ktorá vetva sa má vykonať. Toto je veľmi rýchly, deterministický proces zahŕňajúci jediné porovnanie (alebo sériu booleovských operácií, ktoré možno považovať za ohraničené). Moderné procesory sú vysoko optimalizované pre podmienené vetvenie.

* nezávisle od veľkosti vstupu: Rozhodnutie o vykonaní bloku „if“ alebo bloku „else“ (alebo ani ak neexistuje „inak“) nezávisí od veľkosti vstupných údajov spracovaných okolitým algoritmom. Závisí to iba od samotného stavu.

Prečo O (1) môže byť zavádzajúci (záleží na kontexte!)

Zatiaľ čo samotný príkaz `if` * je o (1), * kód * vo vnútri bloku„ if` blok alebo `else` môže mať akúkoľvek časovú zložitosť. To je rozhodujúce. Zvážte tieto scenáre:

1. o (1) if-blok:

`` `Python

Ak x> 5:

y =10 # o (1) priradenie

z =x + y # o (1) pridanie

inak:

y =20 # o (1) priradenie

`` `

V takom prípade príkaz „if“ a kód v * oboch * vetinách sú o (1). Celková zložitosť tohto úryvku je O (1).

2. o (n) if-blok:

`` `Python

ak Len (my_list)> 0:

pre ja v rozsahu (Len (my_list)):# o (n) slučka

tlač (my_list [i])

inak:

tlač ("Zoznam je prázdny") # o (1)

`` `

Ak je podmienka pravdivá, vykonávate slučku, ktorá iteruje prostredníctvom `my_list`, takže zložitosť„ if` vetvy o (n). Ak je podmienka nepravdivá, vykonávate O (1) kód. Zložitosť * najhoršieho prípadu celého tohto bloku kódu je O (n), pretože príkaz „if“ môže viesť k vykonaniu kódu O (N).

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

`` `Python

Ak podmienka:

pre i v rozsahu (n):

pre j v rozsahu (n):

# Niektoré operácie O (1)

prejsť

inak:

# O (1) Prevádzka

prejsť

`` `

V tomto príklade sa časová zložitosť stáva O (n^2) kvôli vnoreným slučkám vo vyhlásení „if“, aj keď vyhodnotenie podmienky „if“ je stále O (1).

v súhrne

* Logika vetvenia príkazu `if` je o (1).

* Celková časová zložitosť kódu obsahujúceho príkaz „if` úplne závisí od zložitosti kódu * vo vnútri * blokov` if` a `else`. Blok s najvyššou zložitosťou bude dominovať.

* Pri analýze algoritmov musíte zvážiť najhorší scenár, ktorý zvyčajne zahŕňa blok „If“ s vykonaním najvyššej zložitosti.

Preto, zatiaľ čo môžete povedať, že vyhlásenie „if“ samotný * trvá konštantný čas, musíte Analyzujte kód vo vnútri vetiev, aby ste určili skutočnú časovú zložitosť kódového bloku obsahujúceho „if“. Zamerajte sa na dominantný termín (kód kódu, ktorý bude trvať najdlhšie, aby sa dosiahla, s rastúcou veľkosťou vstupu).

• Predchádzajúca strana: Aký je význam použitia serializovanej premennej v programovacích jazykoch? 
• Ďalšia strana: Akú úlohu hrá tlmočník pri programovaní a ako sa líši od kompilátora?