H6 harjutusülesanded sorteerimine
Kool: Tallinna Tehnikaülikool (TalTech, TTÜ)
Aine: Algoritmid ja andmestruktuurid - ICD0001
Kategooria: Informaatika
Postitatud: 21 detsember 2024
Postitaja: rig14
Kirjeldus
O(m) O(n)O(ln m) lg m keerukuse saame kasutades binaar-otsingupuud kuna O(m) O(n)O(ln m) järelikult lõppkeerukus O(nlg m) intersection(MN) // create binary search tree from M tree BST(M) // O(m) result for (element in N) // O(n) if (tree.contains(element)) // O(lg m) result.add(element) return result NB Kiiremini saaks siis kui BST koostatkas N-ist kuna n m ja otsimist on rohkem O(1) answer(ab count) result countb-1 - counta return result Kus N - arvude masiiv vahemikus 0...k k - vahemiku lõpp n - masiivi suurus a - otsitava vahemiku algus b - otsitava vahemiku lõpp 1. Loeme kokku arvude sinemissageduse 2. lisame iga arvu esinemissagedusele juurde eelneva arvu esinemissageduse O(k) O(k) O(n) O(2k n) O(k n) rangeFinder(N k n a b) count prepare(N k n) return answer(abcount) prepare(N k n) count for i0 to k // O(k) counti0 for j0 to n // O(n) countNj 1 for i 0 to k // O(k) if (i 0) continue c…