Mam napisać algorytm dokonujący dokładnie tyle porównań przy sortowaniu 4 kluczy w przypadku pesymistycznym.
Hmm, nie mam pojęcia, o co chodzi w tym zadaniu. Dokładnie tyle porównań? Myślę, że może to wynika z własności drzew binarnych, zacytuję:
"Każdy algorytm Alg sortujący ciąg n elementowy przez porównania musi wykonać co najmniej |lg n!| (| | - oznacza funkcję sufit) porównań w najgorszym przypadku"
Okej, tylko jak to napisać? Ma ktoś pomysł?
Każdy algorytm ma inny przypadek pesymistyczny.
No właśnie, ale taka jest treść zadania. Na pewno nie błąd, należy zwrócić uwagę, że jest napisane - algorytm przy sortowaniu, który przez porównania musi wykonać co najmniej |lg n!|. No, na tym polega mój problem, jak to napisać?
Zrób to na if'ach skoro masz konkretną ilość elementów - to żaden problem.
Ale w tym zadaniu na pewno jest błąd bo dolna granica asymptotyczna sortowania przez porównywnie to O(nlog(n)) a nie log(n!)...