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