"saamude" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

Hinnangud hakkavad kehtima alles N-i suurte väärtuste korral. O. def: Funktsioon g(N) on O(f(N)), kui leiduvad konstandid C0 ja N0, nii et g(N)N0 korral • O(g(n)) on funksioonide hulk, mis ei kasva kiiremini kui g(n). Algoritmid ja andmestruktuurid 2015 2  • g(n) on funktsioon, mis kirjeldab algoritmi saamude arvu ja sellest tulenevalt tööaja seost sisendi mahuga (n). Näiteks võib funktsiooniks g(n) olla n, n2 jms Konstant C0-ga: • püütakse likvideerida vead, mis tekivad matemaatiliselt sammude väljaarvutamisel või programmi analüüsides ebaoluliste lausete vahelejätmise tõttu • et võimaldada klassifitseerida algoritmid tööaja ülemise piiri järgi 1.4 Erinevad keerukusklassid: kirjeldus, näited