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

Odpowiedz Nowy wątek
2018-09-14 12:47
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 :/

edytowany 1x, ostatnio: Sandra, 2018-09-14 12:47

Pozostało 580 znaków

2018-09-14 12:58
1

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

edytowany 1x, ostatnio: przemyslowiec, 2018-09-14 12:58

Pozostało 580 znaków

2018-09-14 12:59
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


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2018-09-14 13:00

Pozostało 580 znaków

2018-09-14 13:04
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 :)

edytowany 1x, ostatnio: Sandra, 2018-09-14 13:13

Pozostało 580 znaków

2018-09-18 14:52
1

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).


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 2x, ostatnio: MarekR22, 2018-09-18 14:55
Jasnym jest że autorka pyta o wzrost czasu wykonania jeśli rozmiar danych wzrośnie 2^16 krotnie ;) - Shalom 2018-09-18 14:59
no ale Merge sort podstawa logarytmu nie ma znaczenia, bo log_a(n) = log n) / log(a). A log(a) to jest czynnik stały odrzucany w notacji o, więc nie można powiedzieć na pewno, iż wzrost danych o czynnik 2^16 da dla "Merge sort" zmianę o czynnik 2^20. - MarekR22 2018-09-18 15:06

Pozostało 580 znaków

2018-09-18 21:54
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).

edytowany 1x, ostatnio: enedil, 2018-09-18 21:59

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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