Darmowe pytania testowe z tematu Algorytmy i złożoność z podpowiedziami i wyjaśnieniami, na trzech poziomach: kluczowe pojęcia i fakty, stosowanie pojęć, przypadki i analiza.
Która klasa złożoności rośnie najszybciej dla dużych n?
Dobra robota. Chcesz kolejne zadanie?Gotowy na następne? 5 nowych zadań każdego dnia, w każdym temacie.
Algorytm to skończona lista precyzyjnych kroków rozwiązujących problem, na przykład sortowanie listy albo szukanie nazwiska w książce telefonicznej.
Dwa algorytmy mogą rozwiązywać ten sam problem, ale zajmować bardzo różną ilość czasu. Złożoność opisuje, jak rośnie nakład pracy, gdy dane wejściowe się powiększają.
Rozmiar danych wejściowych oznacza się n: liczba elementów do posortowania, długość listy, liczba wierzchołków grafu.
Wyobraź sobie szukanie nazwiska w książce telefonicznej liczącej 1000 stron. Przeczytanie każdej strony zajmuje do 1000 kroków. Otwieranie jej w połowie i za każdym razem dzielenie na pół zajmuje około 10 kroków.
Złożoność czasowa zlicza kroki. Złożoność pamięciowa zlicza dodatkową pamięć. Obie zapisuje się jako funkcję n.
Zwykle rozważa się przypadek pesymistyczny: największy nakład pracy spośród wszystkich danych o rozmiarze n. Czasem pytają zamiast tego o przypadek średni lub optymistyczny.
Odpowiedź: 4 sekundy. Podwojenie n mnoży n² przez 2² = 4, więc czas rośnie z około 1 do około 4 sekund. 2 sekundy byłyby odpowiedzią dla wzrostu liniowego, a 8 dla n³.
Notacja dużego O zachowuje tylko to, co ważne dla dużych n. Odrzucasz stałe współczynniki i zostawiasz tylko najszybciej rosnący składnik.
Dla n = 1000 składnik n² wynosi 3 000 000, a 5n tylko 5000. Mniejsze składniki prawie nie zmieniają sumy.
Te klasy pojawiają się raz po raz, od najwolniejszego do najszybszego wzrostu:
Duże O to ograniczenie górne: nakład pracy rośnie co najwyżej tak szybko. Ω (duża omega) to ograniczenie dolne, a Θ (duża theta) to ograniczenie dokładne, zarazem górne i dolne.
Podstawa logarytmu nie ma znaczenia w notacji dużego O, ponieważ logarytmy o różnych podstawach różnią się tylko stałym czynnikiem.
Odpowiedź: O(n²). Dla dużych n dominuje składnik n², a stały czynnik 2 się odrzuca. O(n) zachowuje zły składnik, a O(2n²) zapomina odrzucić stałą.
Kilka algorytmów pojawia się w prawie każdym kursie. Ucz się ich złożoności jako faktów.
Funkcja rekurencyjna wywołuje samą siebie dla mniejszych danych, aż dojdzie do przypadku bazowego, na który odpowiada bezpośrednio. Jej czas działania zapisuje się jako równanie rekurencyjne:
Warto znać trzy idee projektowania. Dziel i zwyciężaj dzieli, rozwiązuje i łączy. Algorytm zachłanny w każdym kroku wybiera lokalnie najlepszą opcję. Programowanie dynamiczne zapamiętuje odpowiedzi na nakładające się podproblemy, więc każdy liczy się tylko raz.
Odpowiedź: O(n²). Przy złych elementach rozdzielających każdy podział zostawia n − 1 elementów po jednej stronie, co daje O(n²). O(n log n) to jego przypadek średni i przypadek pesymistyczny sortowania przez scalanie.
Aby znaleźć złożoność czasową fragmentu kodu:
W pytaniu teoretycznym najpierw nazwij algorytm lub ideę, którą opisuje, potem przypomnij sobie jego złożoność i warunki (posortowane dane, nieujemne wagi, nakładające się podproblemy).
Przejdź przez każdy krok. Spróbuj przewidzieć następny, zanim go odsłonisz.
Jaka jest złożoność czasowa tego kodu? for i = 1 to n: (j = 1; while j < n: j = j × 2)
n to liczba, do której biegną pętle.
i biegnie od 1 do n co 1, więc pętla zewnętrzna wykonuje się n razy.
j przyjmuje wartości 1, 2, 4, 8, … i kończy, gdy dojdzie do n. Po k rundach j = 2k, więc pętla kończy się po około log₂ n rundach.
Pętla wewnętrzna znajduje się wewnątrz zewnętrznej, więc liczby się mnoży.
Dla n = 1024 pętla wewnętrzna wykonuje się log₂ 1024 = 10 razy, więc ciało pętli wykonuje się 1024 · 10 = 10 240 razy. To znacznie mniej niż n² = 1 048 576.
O(n log n)
Odpowiedź: O(n). Pętle występujące jedna po drugiej się dodaje: n + n = 2n, a stałą się odrzuca, więc wynik to O(n). O(n²) byłoby poprawne tylko wtedy, gdyby jedna pętla znajdowała się wewnątrz drugiej.
P zawiera problemy, które można rozwiązać w czasie wielomianowym. NP zawiera problemy, których rozwiązania można sprawdzić w czasie wielomianowym. Każdy problem z P należy do NP; czy P = NP, nadal nie wiadomo.
Ucz się krok po kroku w aplikacjiUcz się krok po kroku w aplikacji
Która notacja opisuje górne ograniczenie tempa wzrostu?
O daje ograniczenie górne, Ω ograniczenie dolne, a Θ ograniczenie dokładne (asymptotycznie ścisłe).
W posortowanej tablicy szukasz dwóch elementów o sumie równej celowi, przesuwając po jednym wskaźniku z każdego końca do środka. Jaka jest złożoność czasowa?
Gdy suma jest za mała, lewy wskaźnik przesuwa się w prawo, gdy za duża, prawy w lewo, więc kroków jest najwyżej n.
Algorytm Strassena mnoży macierze, używając 7 zamiast 8 rekurencyjnych mnożeń bloków o połowie rozmiaru. Jaki jest jego czas działania?
Przy a = 7 i b = 2 nlog₂ 7 dominuje nad pracą O(n²) na dodawania, co daje około n2,81.
Dwa algorytmy mogą rozwiązywać ten sam problem, ale zajmować bardzo różną ilość czasu. Złożoność opisuje, jak rośnie nakład pracy, gdy dane wejściowe się powiększają.
Rozmiar danych wejściowych oznacza się n: liczba elementów do posortowania, długość listy, liczba wierzchołków grafu.
Każde pytanie ma cztery odpowiedzi i tylko jedna jest poprawna. Utknąłeś? Najpierw otwórz małą podpowiedź, a pełne wyjaśnienie dopiero wtedy, gdy go potrzebujesz.