Kwalifikacja: INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych
Zawód: Technik informatyk , Technik programista
Kategorie: Programowanie webowe Algorytmy i podstawy informatyki
Jaką złożoność obliczeniową mają problemy związane z przeprowadzaniem operacji na łańcuchach lub tablicach w przypadku dwóch zagnieżdżonych pętli przetwarzających wszystkie elementy?
Odpowiedzi
Informacja zwrotna
Odpowiedź O(n²) jest jak najbardziej trafna. Wiesz, jak to działa? Gdy masz dwie zagnieżdżone pętle, które przetwarzają elementy w kolekcji, to liczba operacji rośnie kwadratowo w zależności od tego, ile tych elementów masz. Dla n elementów w tablicy, każda z tych n elementów wymaga n operacji w drugiej pętli, co daje razem n*n, czyli n². Przykłady? Algorytmy sortowania bąbelkowego czy przez wstawianie świetnie to ilustrują – obydwa działają w czasie O(n²). Pamiętaj, że jako programiści musimy zwracać uwagę na złożoność algorytmów, bo to wpływa na wydajność naszych aplikacji, szczególnie gdy mamy do czynienia z dużymi zbiorami danych. Dobrze jest próbować optymalizować złożoność, żeby nie wpaść w pułapki wydajnościowe. No i fakt, przy problemach, gdzie musimy porównywać wszystkie elementy, O(n²) to często jedyna opcja, która się sprawdza.