Najpierw spróbuj odpowiedzieć sam, potem odsłoń odpowiedź. Filtruj po dziale, żeby przerobić jeden temat naraz.
Pytania 41–42 z 42
Algorytm polega na dwukrotnym wykonaniu prostych operacji na każdym elemencie tablicy. Złożoność obliczeniowa takiego problemu to
Algorytm polega na dwukrotnym wykonaniu prostych operacji na każdym elemencie tablicy. Złożoność obliczeniowa takiego problemu to
Dlaczego? Stała liczba operacji (tu 2) na każdym z n elementów to 2n, a stałe się pomija, więc złożoność jest O(n).
W celu optymalizacji programu działającego na uporządkowanym zbiorze można zastosować metodę wyszukiwania
W celu optymalizacji programu działającego na uporządkowanym zbiorze można zastosować metodę wyszukiwania
Dlaczego? W posortowanym zbiorze wyszukiwanie binarne dzieli zakres na pół w każdym kroku, więc działa w O(log n).