Big-O keerukuse uurija

Big-O kirjeldab, kuidas töö maht kasvab sisendi suuruse kasvades. Üksik tsükkel kasvab enam-vähem N-iga, pesastatud tsüklid sageli N²-ga ja hargnev rekursioon võib kasvada eksponentsiaalselt. Oluline õppetund on skaala: väikese N juures näevad paljud lähenemised sarnased välja, kuid suurema N juures domineerib täitmisaega kasvuklass.

Kõige selgemini tajub kasvuklassi, kui sisendit kahekordistada ja jälgida, mis tööhulgaga juhtub. O(log N) korral see peaaegu ei muutu — kahendotsing leiab ühe elemendi miljoni seast umbes 20 võrdlusega. O(N) korral töö kahekordistub ja O(N²) korral neljakordistub. Liiguta selles tööriistas N-i ja vaata, kuidas vahed kasvavad nähtamatust tohutuks.

Madalam kasvuklass ei taga kiiremat programmi. Arvutiteadlased nimetavad erandeid galaktilisteks algoritmideks: parema Big-O-ga meetodid, mille peidetud konstanttegur on nii tohutu, et nad edestavad lihtsamaid meetodeid alles sisendite juures, mis on suuremad kui miski füüsilises universumis. Mitut rekordilist maatriksite korrutamise algoritmi ei kasutata praktikas just sel põhjusel — Big-O jätab vaikimisi kõrvale konstandid, mis tegeliku kiiruse määravad.