"eiteata" - 1 õppematerjal

Algoritmi ajaline keerukus

Seda tähistatakse kujul O(g(n)) . Näiteks O(n2) . Def. Olgu f ja g naturaalarvuliste argumentidega ja positiivsete väärtustega funktsioonid. Siis f on O(g(n)) parajasti siis kui leidub c>0 ja N>0 nii, et f(n)=N korral. Lihtkeeles öeldakse et f on O(g(n)) kui küllalt suurte n väärtuste korral f(n)eiteata polünomiaalse keerukusega algoritmi, nimetatakse raskesti lahenduvaks (näiteks seljakoti ülesanne). Algoritmi nende osade ajaline keerukus, mis ei sõltu n-st on O(1). Iteratiivse algoritmi ajalise keerukuse hindamiseks leitakse tsüklite kordamise käigus sooritatavate põhioperatsioonide arv. Nii saame lineaarse tsükli ajalise keerukuse hinnanguks O(n) (tsüklis eeldatakse üks põhitehe). Ülesanne: Leida ajalise keerukuse hinnang lihtsale kahekordsele tsüklile, mis sisaldab