void wypisz(int n) {
for (int i = 1; i <= n; i++) {
System.out.println("Wykonanie operacji po raz " + i);
}
System.out.println("Wykonanie kolejnej operacji!");
}
Złożoność obliczeniowa prezentowanego kodu wynosi:
W tym zadaniu kluczowe jest zauważenie, że jedynym fragmentem kodu, który realnie „rośnie” wraz ze wzrostem n, jest pętla for. Pętla wykonuje się od i = 1 do i <= n, czyli dokładnie n razy. W każdej iteracji wykonywana jest jedna instrukcja wypisania tekstu na konsolę: System.out.println("Wykonanie operacji po raz " + i);. To jest stały zestaw operacji w każdej iteracji, nie pojawia się żadna zagnieżdżona pętla, żadne rekurencyjne wywołania ani inne konstrukcje, które by powodowały większy wzrost liczby operacji.
Z tego powodu całkowita liczba operacji tego algorytmu jest proporcjonalna do n, a w notacji dużego O zapisujemy to jako O(n). Dodatkowe wywołanie System.out.println("Wykonanie kolejnej operacji!"); po zakończeniu pętli ma z punktu widzenia złożoności asymptotycznej znaczenie stałe – to jest jedna instrukcja, więc dokładamy tylko +1 do liczby operacji. Standardowo w analizie algorytmów takie stałe pomijamy, bo interesuje nas zachowanie dla bardzo dużych n.
W praktyce taki schemat O(n) pojawia się non stop: przechodzenie po elementach tablicy, listy, sprawdzanie każdego rekordu z pliku, proste filtrowanie danych. Moim zdaniem warto wyrobić sobie nawyk: widzisz pojedynczą pętlę, bez dodatkowych zagnieżdżeń i bez skoków zależnych od innych zmiennych – bardzo często będzie to właśnie złożoność liniowa. W dobrych praktykach projektowania algorytmów przyjmuje się, że O(n) jest zazwyczaj akceptowalne dla sporych danych, bo czas rośnie wprost proporcjonalnie do liczby elementów. Dopiero gdy pojawiają się pętle w pętlach, trzeba się bardziej martwić o wydajność.
Warto też pamiętać, że operacja wejścia/wyjścia (I/O), jak wypisywanie na konsolę, jest w rzeczywistości dość kosztowna, ale w analizie teoretycznej zakładamy, że to jedna jednostkowa operacja na iterację. Dzięki temu możemy porównywać różne algorytmy w sposób ogólny, niezależny od konkretnej maszyny czy implementacji.
Z tego powodu całkowita liczba operacji tego algorytmu jest proporcjonalna do n, a w notacji dużego O zapisujemy to jako O(n). Dodatkowe wywołanie System.out.println("Wykonanie kolejnej operacji!"); po zakończeniu pętli ma z punktu widzenia złożoności asymptotycznej znaczenie stałe – to jest jedna instrukcja, więc dokładamy tylko +1 do liczby operacji. Standardowo w analizie algorytmów takie stałe pomijamy, bo interesuje nas zachowanie dla bardzo dużych n.
W praktyce taki schemat O(n) pojawia się non stop: przechodzenie po elementach tablicy, listy, sprawdzanie każdego rekordu z pliku, proste filtrowanie danych. Moim zdaniem warto wyrobić sobie nawyk: widzisz pojedynczą pętlę, bez dodatkowych zagnieżdżeń i bez skoków zależnych od innych zmiennych – bardzo często będzie to właśnie złożoność liniowa. W dobrych praktykach projektowania algorytmów przyjmuje się, że O(n) jest zazwyczaj akceptowalne dla sporych danych, bo czas rośnie wprost proporcjonalnie do liczby elementów. Dopiero gdy pojawiają się pętle w pętlach, trzeba się bardziej martwić o wydajność.
Warto też pamiętać, że operacja wejścia/wyjścia (I/O), jak wypisywanie na konsolę, jest w rzeczywistości dość kosztowna, ale w analizie teoretycznej zakładamy, że to jedna jednostkowa operacja na iterację. Dzięki temu możemy porównywać różne algorytmy w sposób ogólny, niezależny od konkretnej maszyny czy implementacji.
Kod z zadania jest klasycznym przykładem na to, jak wygląda złożoność liniowa i gdzie łatwo się pomylić przy jej ocenie. Wiele osób, widząc pętlę, próbuje od razu dopasować jedną z „groźnie” wyglądających złożoności, jak n² czy n!, bo brzmią bardziej skomplikowanie. Tymczasem analiza powinna być spokojna i oparta na policzeniu, ile razy realnie wykonuje się dana instrukcja.
W zaprezentowanej funkcji mamy jedną pętlę for, która startuje od 1 i kończy na n, więc iteruje dokładnie n razy. W każdej iteracji wykonywane jest jedno wywołanie System.out.println z prostą konkatenacją tekstu i zmiennej i. To oznacza, że liczba tych wywołań rośnie liniowo wraz z n. Po pętli jest jeszcze jedno, pojedyncze wypisanie. Dodanie stałej liczby operacji (tu: +1) nie zmienia charakteru wzrostu – w notacji O() takie stałe są pomijane, bo dla dużych n nie mają znaczenia.
Złożoność O(n²) pojawiłaby się, gdyby wewnątrz tej pętli była kolejna pętla, zależna również od n, np. for (int j = 1; j <= n; j++). Wtedy liczba iteracji wyniosłaby n * n, czyli n². W tym kodzie tego nie ma, więc przypisywanie mu n² jest typowym przeszacowaniem związanym z automatycznym kojarzeniem „pętla = kwadrat”. To błąd myślowy: jedna pętla → O(n), dwie zagnieżdżone → często O(n²), ale trzeba to zawsze policzyć, a nie zgadywać.
Z kolei O(n!) opisuje algorytmy ekstremalnie kosztowne, jak pełne permutowanie elementów (np. brutalne generowanie wszystkich możliwych ustawień). W naszym przykładzie nie ma ani permutacji, ani rekurencji, ani eksplodującej liczby kombinacji. Jedynie proste przejście po kolejnych liczbach od 1 do n, więc factorial tutaj kompletnie nie pasuje.
O(1) oznaczałoby, że czas działania nie zależy w ogóle od n – na przykład pojedyncze wywołanie metody, prosta operacja arytmetyczna, odczyt elementu z tablicy po indeksie. Tutaj jednak im większe n, tym więcej razy wykonuje się pętla i tym dłużej program działa. To już wyklucza złożoność stałą.
Z mojego doświadczenia warto zawsze zadać sobie dwa pytania: ile razy wykona się pętla i czy wewnątrz niej nie ma kolejnych pętli lub wywołań kosztownych algorytmów. Taka spokojna analiza krok po kroku pozwala uniknąć mylenia złożoności liniowej z kwadratową, stałą czy nawet silnią.
W zaprezentowanej funkcji mamy jedną pętlę for, która startuje od 1 i kończy na n, więc iteruje dokładnie n razy. W każdej iteracji wykonywane jest jedno wywołanie System.out.println z prostą konkatenacją tekstu i zmiennej i. To oznacza, że liczba tych wywołań rośnie liniowo wraz z n. Po pętli jest jeszcze jedno, pojedyncze wypisanie. Dodanie stałej liczby operacji (tu: +1) nie zmienia charakteru wzrostu – w notacji O() takie stałe są pomijane, bo dla dużych n nie mają znaczenia.
Złożoność O(n²) pojawiłaby się, gdyby wewnątrz tej pętli była kolejna pętla, zależna również od n, np. for (int j = 1; j <= n; j++). Wtedy liczba iteracji wyniosłaby n * n, czyli n². W tym kodzie tego nie ma, więc przypisywanie mu n² jest typowym przeszacowaniem związanym z automatycznym kojarzeniem „pętla = kwadrat”. To błąd myślowy: jedna pętla → O(n), dwie zagnieżdżone → często O(n²), ale trzeba to zawsze policzyć, a nie zgadywać.
Z kolei O(n!) opisuje algorytmy ekstremalnie kosztowne, jak pełne permutowanie elementów (np. brutalne generowanie wszystkich możliwych ustawień). W naszym przykładzie nie ma ani permutacji, ani rekurencji, ani eksplodującej liczby kombinacji. Jedynie proste przejście po kolejnych liczbach od 1 do n, więc factorial tutaj kompletnie nie pasuje.
O(1) oznaczałoby, że czas działania nie zależy w ogóle od n – na przykład pojedyncze wywołanie metody, prosta operacja arytmetyczna, odczyt elementu z tablicy po indeksie. Tutaj jednak im większe n, tym więcej razy wykonuje się pętla i tym dłużej program działa. To już wyklucza złożoność stałą.
Z mojego doświadczenia warto zawsze zadać sobie dwa pytania: ile razy wykona się pętla i czy wewnątrz niej nie ma kolejnych pętli lub wywołań kosztownych algorytmów. Taka spokojna analiza krok po kroku pozwala uniknąć mylenia złożoności liniowej z kwadratową, stałą czy nawet silnią.