Przeciętna złożoność algorytmów - ile razy MergeSort jest szybszy od BubbleSort

0

Bardzo proszę o sprawdzenie czy poprawnie wyliczyłam przeciętną złożoność algorytmu. Nie pokrywa mi się z gotową odpowiedzią, która niby powinna być poprawna ale jakoś tego nie widzę

Ile razy przeciętnie szybszy jest MergeSort od BubbleSort dla n=2^16

MS - n*log_2(n)
BS - 1/2n^2

Finalnie wyszło mi 2^25/16

W odpowiedziach widnieje 2048 :/

1

Jest tak jak w odpowiedzi 2048, wolframalpha jest pomocny czasem: wynik

2

Nie bardzo rozumiem twoje obliczenia...
Bubble sort dla rozmiaru danych powiększonego 2^16 krotnie wykona 1/2 * (n*2^16)^2 = 2^31 * n^2 operacji.
Merge sort dla rozmiaru danych powiększonego 2^16 krotnie wykona n*2^16 * log2(n*2^16) = 2^16 * 2^4 * n*log(n) = 2^20 * n*log(n)
Bubble sort zwolnił 2^31 razy a merge sort 2^20 razy, więc mamy 2^31/2^20 = 2^11 = 2048

0

Ok dzięki już widzę gdzie mam błąd. Przy logarytmie zamiast po tym jak wyszło 16 zrobić z tego 2^4 przepisałam tą 16 i później już jak patrzyłam to nie mogłam znaleźć tego błędu jakoś

W kazdym razie wielkie dzięki za szybkie przywrócenie na tor :)

2

Ile razy przeciętnie szybszy jest MergeSort od BubbleSort dla n=2^16

To pytanie jest bezsensu! NIE MA PRAWIDŁOWEJ ODPOWIEDZI!
Złożoność obliczeniowa w notacji o wcale nie oznacza, że dla n=2^16 jeden algorytm bezie szybszy dokładnie o X.
Złożoność obliczeniowa w notacji o opisuje jak problem się skaluje wraz zależnie ot danych wejściowych. Nic więcej
Nie można porównywać tych wartości dla rożnych algorytmów.
W notacji o odrzuca się automatycznie wszelkie stałe czynniki, więc o(263*n) z o(n) są sobie równoważne i wcale to nie oznacza, że drugi algorytm będzie szybszy o 263 razy od pierwszego.

Dla "Bubble Sort" masz o(n^2) i to znaczy, że algorytm będzie się wykonywał 4 razy dłużej dla 2*n elementów niż dla n elementów. Nic więcej.
Dla "Merge Sort" masz o(n * log n) i podstawa tego algorytmu nie ma znaczenia (może być log_2 może log_10 może log_e). i tu nie da się powiedzieć, o ile szybszy będzie algorytm, jeśli dane będą 2 razy większe, będzie to skala 2 log (n) (podstawa logarytmu jest nieustalona).

0

@MarekR22: z całym szacunkiem, nie masz racji, w zadaniu nie napisano że złożoności są O(f(n)), czy też jak to piszesz o(f(n)), ale dokładnie f(n). Więcej, nawet jeśli algorytm jest O(n^2), nie znaczy to że będzie 4 razy wolniejszy dla 2 razy większych danych, duże O jest jedynie ograniczeniem górnym. A jeśli jest o(n^2), to to co napisałeś niestety nie ma sensu, bo małe o mówi że w granicy, czas wykonania jest znacznie mniejszy niż n^2, czyli nawet nie istnieje przypadek takiej funkcji, która dla każdych argumentów spełnia zależność f(2n) = 4f(n).

1 użytkowników online, w tym zalogowanych: 0, gości: 1