Matematyka.pl

Absolutnie wspólnie. Drużyna dostaje komplet zadań, drużyna go oddaje.

Tak się składa, że nawet w tym samym miejscu, choć bardzo dawno temu

Czy tylko ja mam wrażenie, że trzy spośród zadań są prostackie i łopatologiczne, a jeszcze jedno nieco tylko sprytniejsze, ale wciąż nietrudne?

[edit:] ok, nie doceniłem drugiego dnia. Ale pierwszy wciąż mi się nie podoba.

Masz oczywiście rację, nie doczytałem. OK, czyli wykonują się albo 2 porównania (jeśli nie poprawił się element maksymalny), albo jedno (jeśli się nie poprawił). Czyli wykonamy n-1 porównań plus tyle dodatkowych, ile razy napotkamy element większy niż wszystkie poprzednie. Jak policzyć oczekiwaną li...

Jeśli liczysz porównania (!), to wszystkie trzy złożoności masz takie same - przecież wszystkie 2n-2 porównań wykona się zawsze.

To mi się nie podoba. Jeśli to ma losować element spomiędzy indeksów l a r, to tego nie robi z pewnością. Losuje spomiędzy l+1 a l+r, co wykrzacza algorytm.

Jeśli umówimy się na konkretną implementację QuickSorta, to oczywiście - przecież dla każdego algorytmu, który sortuje przez porównania da się utworzyć drzewo decyzyjne.

- p(d) - prawdopodobieństwo wystąpienia danej d No właśnie tego potrzeba - skąd wiedzieć, jakie jest prawdopodobieństwo wystąpienia danego zestawu liczb w tablicach? Rozwiążmy to zadanie przy dość rozsądnym założeniu, że liczby do tablic losowane są jednostajnie z przedziału [0, K-1] . Skorzystam t...

Ale samej definicji średniej złożoności nie masz podanej? Bo to na ogół nie jest średnia arytmetyczna...
No to nie masz wyboru: załóż, że liczby w tablicach są losowane z przedziału [0, K]. Jakie masz szanse zakończyć algorytm w danym, ustalonym kroku?

Średnia złożoność nie zależy od optymistycznej (wspominałem, że to bezsensowne pojęcie?) i pesymistycznej.

Hm, może u Ciebie jest inna definicja średniej złożoności...możesz ją przytoczyć?

Chodzi o to, że złożoność będzie inna, jeśli n jest małe, a liczby losowane z bardzo dużego przedziału, a inna jeśli liczby są zerami lub jedynkami. "Średnia złożoność" nie oznacza "średnia z dwóch różnych algorytmów". Oznacza "jeśli programowi damy wszystkie możliwe zestawy...

Tak. Odpowiedź w iii) jest w związku z tym \(\displaystyle{ n^2 \log n}\), w (iv) już dojdziesz sam

b) działa, jeśli wykładniki wyjdą dokładnie równe. Na przykład przy klasycznym równaniu MergeSorta:

\(\displaystyle{ T(n) = 2T(n/2) + n}\)

Tutaj \(\displaystyle{ f(n) = n}\) i \(\displaystyle{ n^{log_ba} = n}\). Przy czym stała przy \(\displaystyle{ f(n)}\) nie ma znaczenia: równanie \(\displaystyle{ T(n) = 2T(n/2) + 20 n}\) robiłoby się tak samo.

Nie. W pierwszym porównujesz \(\displaystyle{ f(n)}\) (czyli \(\displaystyle{ n^2}\)) i \(\displaystyle{ n^{log_ba}}\), czyli \(\displaystyle{ n}\). Większy wykładnik ma to pierwsze, więc działa podpunkt a).
W drugim analogicznie działa c).

Wygląda nieźle.