T2 Final Algoritmid ja andmestruktuurid
Kool: Tallinna Tehnikaülikool (TalTech, TTÜ)
Aine: Algoritmid ja andmestruktuurid - ICD0001
Kategooria: Informaatika
Postitatud: 21 detsember 2024
Postitaja: rig14
Kirjeldus
H2 harjutusülesanded 2-1 Näidake kuidas leiate järgneva algoritmi keerukusklassi O-notatsioonis (tulemus O(n3)) 1 1 1 n O(in) i 1 inn2 n2 O(n2) 1 1 n2nO(n3) O(n2) 0.5 1 n (n2-n) / 2 1 0.5n2 0.5log(n) O(n2) 1 O(log(n) 1 floor(log3(k))1 floor(log3(n3))1 1 mystery(int n) int i j k v for(i 0 i n i) for(j i j 0 j--) v vij if(paarisarv(i)) for(k n k nn kk2) v kv else k nnn while(k 0) v-- k k/3 return(v) Mõtlemise lihtsustamiseks võite esialgu määrata osade keerukuse eraldi 1 (0.5n2-0.5n) O(n2) 1 (n2-n) / 2 mystery(int n) for(k n k nn kk2) v kv 1 1 floor(log3(n3))1O(log(n)) 1 floor(log3(k))1 floor(log3(n3))1 mystery(int n) k nnn while(k 0) v-- k k/3 k---iter 1---1 2---1 3---2 4---2 5---2 6---2 7---2 8---2 9---3 10---3 ... 1 1 niO(n) n i i 1 mystery(int n) for(i 0 i n i) for(j i j 0 j--) v vij 2-2 Millised suhetest kas f (g) f (g) f (g) f (g) f (g) on õiged ja miks f g O o n3/2 n log(n) S…