Który z podanych algorytmów operujących na jednowymiarowej tablicy posiada złożoność obliczeniową O(n²)?
Sortowanie bąbelkowe, znane również jako bubble sort, to prosty algorytm sortowania, który działa na zasadzie wielokrotnego przechodzenia przez tablicę i porównywania sąsiadujących ze sobą elementów. Algorytm ten ma złożoność obliczeniową O(n^2), co oznacza, że w najgorszym przypadku liczba operacji porównania wzrasta kwadratowo wraz ze wzrostem liczby elementów w tablicy. Przykładowo, dla tablicy o 5 elementach algorytm może wykonać do 10 porównań. W praktyce sortowanie bąbelkowe jest rzadko stosowane w dużych zbiorach danych ze względu na swoją niską efektywność, jednak jest to dobry przykład do nauki podstaw algorytmów sortujących. Standardy algorytmów sortujących, takie jak te zawarte w podręcznikach algorytmiki, często używają sortowania bąbelkowego jako przykładu do omówienia prostych koncepcji związanych z sortowaniem. Warto zauważyć, że chociaż algorytm ten jest prosty do zrozumienia, jego złożoność czasowa sprawia, że nie jest on praktyczny do stosowania w produkcyjnych rozwiązaniach, gdyż bardziej optymalne algorytmy, jak sortowanie szybkie czy sortowanie przez scalanie, osiągają złożoność O(n log n).
Sortowanie szybkie, znane jako quicksort, to jeden z najbardziej efektywnych algorytmów sortujących, który w przeciętnych przypadkach ma złożoność O(n log n), a w najgorszym przypadku O(n^2) tylko w przypadku, gdy tablica jest już posortowana w sposób odwrotny. Wyszukiwanie binarne jest algorytmem, który wymaga posortowanej tablicy i działa w czasie O(log n), co czyni go znacznie bardziej wydajnym niż sortowanie bąbelkowe. Wypisanie elementów tablicy to operacja o złożoności O(n), gdzie n oznacza liczbę elementów w tablicy. W tej operacji algorytm przegląda każdy element tablicy tylko raz, co czyni ją bardzo efektywną w porównaniu do algorytmów sortujących. Wszelkie złożoności O(log n) oraz O(n) są bardziej optymalne w kontekście operacji na tablicach jednowymiarowych. W związku z tym, jedynie sortowanie bąbelkowe w tej grupie algorytmów charakteryzuje się złożonością O(n^2), co czyni je jedynym właściwym wyborem w kontekście zadanego pytania.