rekurencja i indukcja

lbobiko · Post autor: **lbobiko** » 20 cze 2016, o 18:29

zadanie 1.3-3 z książki "wprowadzenie do algorytmów "

\(\displaystyle{ T(n)= \begin{cases} 2 &\mbox{ jeśli } n=2 \\ 2T \left( \frac{n}{2} \right) + n &\mbox{ jeśli } n = 2^k \mbox{ dla } k > 1 \end{cases}}\)

Jest \(\displaystyle{ T(n) = n lg n.}\)

mam problem z tym że nie wiem skąd wzięło się że \(\displaystyle{ T(n) = n lg n}\) jest równe klasie złożoności duże O \(\displaystyle{ T(n) = n \log _{2} n}\)

Mruczek · Post autor: **Mruczek** » 24 wrz 2016, o 21:39

Wprost z definicji klasy złożoności duże O.

Cytryn · Post autor: **Cytryn** » 24 wrz 2016, o 22:33

Z definicji funkcji mamy \(\displaystyle{ T(2) = 2}\), ale wzór z odpowiedzi mówi mi \(\displaystyle{ T(2) = 2 \log 2}\), czy to nie jest błąd?

Mruczek · Post autor: **Mruczek** » 25 wrz 2016, o 00:01

To jest logarytm dwójkowy, jak zwykle w informatyce. Wychodzi na to samo.

Cytryn · Post autor: **Cytryn** » 25 wrz 2016, o 09:42

Rozumiem. A skąd wiemy, jak zachowuje się funkcja \(\displaystyle{ T}\) na liczbach nieparzystych? Definicja nic o niej nie mówi.

Mruczek · Post autor: **Mruczek** » 25 wrz 2016, o 21:25

Dobra. Rzeczywiście coś jest nie tak z tą definicją funkcji. Wygląda na to, że żeby mówić o dużym O funkcja powinna być określona na liczbach naturalnych, a nie jest. Sama złożoność się zgadza, bo to O szacuje z góry, ale dziedzina nie bardzo, więc chyba faktycznie nie można mówić tutaj o dużym O.

Zaratustra · Post autor: **Zaratustra** » 26 wrz 2016, o 05:56

Mruczek pisze:Dobra. Rzeczywiście coś jest nie tak z tą definicją funkcji. Wygląda na to, że żeby mówić o dużym O funkcja powinna być określona na liczbach naturalnych, a nie jest. Sama złożoność się zgadza, bo to O szacuje z góry, ale dziedzina nie bardzo, więc chyba faktycznie nie można mówić tutaj o dużym O.

Właściwie autor wątku nie powiedział jaka jest dziedzina funkcji... W ogóle autorzy książki mogli tego nie podkreślić - "1.3-3"? "Cormen"? - to gdzieś początek książki - na ogół na tym etapie \(\displaystyle{ n}\) będzie oznaczać ilość danych wejściowych, która jest dyskretna. Czyli mamy funkcje typu \(\displaystyle{ f \colon \mathbb{N} \to \mathbb{R}}\). Jeśli ilość danych jest nieparzysta to zwykle w takim wypadku bierze się podłogę: \(\displaystyle{ \left\lfloor \frac{n}{2} \right\rfloor}\).
Ja bym zakładał niedokładność autorów... To w końcu chyba bardziej informatycy niż matematycy - czyli uznał że dziedzina jest dyskretna. Albo w ogóle funkcję przepisać w ten sposób: \(\displaystyle{ T(n) = 2T \left( \left\lfloor \frac{n}{2} \right\rfloor \right) + n}\) i dopiero się zastanawiać