Pozdrav svima,
danas sam pisao test iz algoritama za sortiranje u Pythonu te sam izgubio bodove na jednom pitanju.
U udžbeniku po kojem radimo piše sljedeće:
O - gornja složenost
Ω - donja složenost
exchange sort (lista) = O(n²), Ω(n²)
selection sort (lista) = O(n²), Ω(n²)
insertion sort (lista) = O(n²), Ω(n)
bubble sort (lista) = O(n²), Ω(n)
quick sort po Hoareu (lista, rekurzija)= O(n²)(u pravilu - O(n log n)), Ω(n)
merge sort (lista) = O(n log n)
bucket sort (iz liste se kreira rječnik, prolazak kroz ključeve for petljom, dodavanje u novu listu) = O(n)
(u udžbeniku za neke algoritme nisu navedene Ω)
Pitanje glasi: Je li exchange sort najjednostavniji algoritam za sortiranje?
Ja sam odgovorio NE, jer bucket sort ima složenost O(n), a exchange O(n²).
Na kraju sam poslije testa našao tvrdnju u udžbeniku da je exchange sort najjednostavniji.
Zanima me da li sam ja pogriješio(ako jesam, molio bih pojašnjenje) ili je to greška u udžbeniku (inače udžbenik ima nekih grešaka)?
Unaprijed hvala,
HrcaA3000
