Zložitosť algoritmu: if/else do loop - ak vyhlásenie, pre-slučky, zložitosť-teória

Zaujímalo by ma, či v takej situácii, ako je nasledujúca (vyhlásenie if / else pod slučkou for), zložitosť by bola O (n) alebo O (n ^ 2):

for character in string:
if character==something:
do something
else:
do something else.

Ďakujem!

odpovede:

Bude to

O (n) if "robiť niečo" a "robiť niečo iné" sú O (1)

O (n ^ 2) ak "urobiť niečo" a "urobiť niečo iné" sú O (n)

V podstate bude zložitosť slučky závisieť od zložitosti jej zložiek a č. slučiek.

Závisí to, čo robíte v inom vyhlásení, ale verím, že je to O (n), pretože najhorší prípad prechádza reťazec n krát.

Jednoducho povedané, O (n) v podstate znamená algoritmusbude trvať toľko času na vykonanie, pretože existujú prvky v n. O (1) znamená, že algoritmus vždy trvá konštantný čas bez ohľadu na to, koľko prvkov je na vstupe. O (n ^ 2) znamená algoritmus počet položiek v štvorci čas (t.j. spomaľuje stále viac a viac, tým väčší je vstup).

Vo vašom prípade robíte rovnakú vec pre každú položku na vstupe raz. if..else je len jedno normálne tvrdenie, ktoré robíte na každú položku raz. Nie zvyšuje ani znižuje runtime / zložitosť. Váš algoritmus je O (n).