Jaką złożoność obliczeniową mają problemy polegające na wykonaniu czynności na łańcuchu lub tabeli w dwóch zagnieżdżonych pętlach działających na wszystkich elementach?
A. O(n!)
B. O(log n)
C. O(n2)
D. O(n)
Pytanie z egzaminu CKE, styczeń 2023 (arkusz EE.09-SG-23.01).
W tym przypadku złożoność wynosi O(n²), bo mamy dwie zagnieżdżone pętle i każda z nich przechodzi po wszystkich elementach łańcucha albo tablicy. Jeśli tablica ma n elementów, to pętla zewnętrzna wykona się n razy, a dla każdego jej obrotu pętla wewnętrzna też wykona n przebiegów. Razem daje to n × n, czyli n² operacji. W praktyce taki schemat pojawia się np. przy porównywaniu każdego elementu z każdym, prostym sortowaniu bąbelkowym, wyszukiwaniu duplikatów metodą „każdy z każdym” albo analizie wszystkich par znaków w napisie. Moim zdaniem to jeden z najważniejszych przykładów, bo od razu pokazuje, czemu algorytm działający dobrze dla 100 elementów może już nieprzyjemnie zwolnić dla 100 000. W dobrych praktykach programistycznych zawsze warto patrzeć na liczbę zagnieżdżonych pętli i sprawdzać, czy da się użyć słownika, zbioru, sortowania albo innej struktury danych, żeby zejść np. do O(n log n) lub nawet O(n). Sama notacja O opisuje tempo wzrostu czasu działania, a nie dokładną liczbę sekund, więc pomija stałe i drobne szczegóły sprzętu.
Przy takim zadaniu najważniejsze jest zauważenie, że opis mówi o dwóch zagnieżdżonych pętlach, które działają na wszystkich elementach. To nie jest zwykłe przejście po tablicy ani po napisie, więc O(n) byłoby za małe. Złożoność liniowa pasuje wtedy, gdy każdy element odwiedzamy mniej więcej raz, na przykład przy sumowaniu wartości w tablicy, liczeniu znaków w tekście albo sprawdzaniu, czy w tablicy istnieje konkretna liczba. Tutaj jednak dla każdego elementu z pętli zewnętrznej uruchamia się pełny przebieg pętli wewnętrznej, więc liczba operacji rośnie dużo szybciej. Z kolei O(log n) kojarzy się raczej z algorytmami, które w każdym kroku mocno zawężają problem, na przykład wyszukiwanie binarne w posortowanej tablicy. Dwie pełne pętle nie dzielą danych na połowy, tylko przeglądają kombinacje elementów, więc logarytm tu nie pasuje. O(n!) oznacza złożoność silniową i występuje przy rozważaniu wszystkich permutacji, np. w naiwnym podejściu do problemu komiwojażera. To jest dużo cięższa klasa niż dwie pętle. Typowy błąd myślowy polega na tym, że ktoś widzi „pętle” i od razu wybiera O(n), nie sprawdzając, czy pętle są jedna po drugiej, czy jedna w drugiej. Z mojego doświadczenia ta różnica jest niby prosta, ale na testach często robi zamieszanie.