INF.03Programowanie
Złożoność obliczeniowa i Notacja Dużego O
Miara efektywności algorytmu opisująca, jak rośnie czas wykonania lub zużycie pamięci wraz ze wzrostem rozmiaru danych wejściowych (n).
Przegląd klas złożoności obliczeniowej:
O(1)(stała) – czas nie zależy od rozmiaru danych (np. pobranie elementu tablicy po indeksietab[5]).O(log n)(logarytmiczna) – bardzo szybka; liczba kroków rośnie logarytmicznie (np. wyszukiwanie binarne w posortowanej tablicy).O(n)(liniowa) – czas rośnie proporcjonalnie do liczby elementów (np. przeszukiwanie liniowe tablicy pętlą).O(n log n)(liniowo-logarytmiczna) – typowa dla optymalnych algorytmów sortowania (QuickSort, MergeSort).O(n²)(kwadratowa) – czas rośnie z kwadratem danych (np. podwójna pętla, sortowanie bąbelkowe, przez wybieranie).
Najczęstsze pułapki na egzaminie INF.03:
- Pytania CKE często proszą o określenie złożoności podwójnej zagnieżdżonej pętli
foriterującej po tablicy – wynosi ona O(n²).
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Złożoność obliczeniowa i Notacja Dużego O lub rozpocznij trening.