Kwalifikacja: INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych
Zawód: Technik informatyk , Technik programista
Kategorie: Algorytmy i podstawy informatyki
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:
Odpowiedzi
Informacja zwrotna
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.