Kwalifikacja: INF.04 - Projektowanie, programowanie i testowanie aplikacji
Zawód: Technik programista
Który z algorytmów ma złożoność O(n2)?
Odpowiedzi
Informacja zwrotna
Bubble Sort to algorytm o złożoności O(n²), co oznacza, że jego czas wykonania rośnie kwadratowo wraz ze wzrostem liczby elementów wejściowych. Algorytm porównuje sąsiadujące elementy i zamienia je miejscami, jeśli są w złej kolejności. Proces ten powtarza się wielokrotnie, aż do uzyskania pełnego posortowania tablicy. Ze względu na swoją prostotę, Bubble Sort jest często wykorzystywany do nauki podstaw algorytmiki, ale w praktyce rzadko stosuje się go do sortowania dużych zbiorów danych, ponieważ jest nieefektywny w porównaniu do bardziej zaawansowanych algorytmów, takich jak QuickSort czy Merge Sort.
Binary Search to algorytm wyszukiwania o złożoności O(log n), który przeszukuje posortowaną tablicę, dzieląc ją na pół w każdej iteracji. Merge Sort ma złożoność O(n log n) i wykorzystuje technikę 'dziel i zwyciężaj', dzieląc tablicę na mniejsze części i łącząc je w odpowiedniej kolejności. Algorytm Dijkstry jest używany do znajdowania najkrótszej ścieżki w grafach i jego złożoność zależy od implementacji – w przypadku zastosowania kopca binarnego wynosi O(E + V log V), gdzie E to liczba krawędzi, a V to liczba wierzchołków.