From 36fe4a4b885bda34e890a52e9ad1605659eeeaaf Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 May 2007 13:45:06 +0200 Subject: [PATCH] Dalsi verze seste prednasky, uz skoro kompletni, ale pred korekturami. --- 6-trideni/6-trideni.tex | 69 +++++++++++++++++++++++++++++++++++------ 1 file changed, 59 insertions(+), 10 deletions(-) diff --git a/6-trideni/6-trideni.tex b/6-trideni/6-trideni.tex index 54a77db..a98bc47 100644 --- a/6-trideni/6-trideni.tex +++ b/6-trideni/6-trideni.tex @@ -48,13 +48,17 @@ Bucket sort ma je \endalgo \h{Lexikografické tøídìní k-tic} -Mìjme $n$ $k$-tic z $ \{1 \ldots R \}^k $ (prvky $k$-tice jsou $ 1 \ldots R $), seøazení $k$-tic slovníkovì (lexikograficky). +Mìjme $n$ $k$-tic prvkù z mno¾iny $ \{1 \ldots R \}^k $.Ùkol zní seøadit $k$-tice slovníkovì (lexikograficky). Mù¾eme pou¾ít metodu rozdìl a panuj, setøídíme nejprve podle první souøadnice $k$-tic a pak se rekurzivnì zavoláme na ka¾dou pøihrádku a tøídíme podle následující souøadnice. Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto: + +\s{Algoritmus:} (tøídìní $k$-tic $ k_1 \ldots k_n $) \algo -\:Pro $ i \leftarrow k $ do $1$ opakuj: -\::BucketSort podle $i$-té souøadnice +\:$ S \leftarrow \{k_1 \dots k_n\} $ +\:Pro $ i \leftarrow k $ do $ 1 $ opakuj: +\::$ S \leftarrow $ BucketSort $ S $ podle $i$-té souøadnice +\:vysledek $ S $ \endalgo Pro pøehlednost v následujícím pozorování oznaème $ l = k - i + 1 $, co¾ pøesnì odpovídá tomu, v kolikátém prùchodu cyklu jsme. @@ -82,15 +86,53 @@ D Pokud bychom zvolili $ Z = konstanta $, èasová slo¾itost bude $\O(\log{R} * n) $, co¾ mù¾e být a¾ $ n * \log{n} $. Zvolíme-li $ Z = n $, dostáváme $ \O({\log{R} \over \log{n}} * n) $, co¾ pro $ R \leq n^\alpha $ znamená $ \O(\alpha * n) $. -% FIXME dopsat prepsat..v reseni \h{Tøídìní øetìzcù} -Mìjme $n$ øetìzcù dlouhých $ l_1, l_2, \ldots, l_n $ tøídíme $ O(n + \sum_{i}{l_i}) $ -Problém: øetìzce nejsou stejnì dlouhé, je potøeba se vyhnout pøehazování mezer - -\h{K èemu je tøídìní dobré?} +Mìjme $n$ øetìzcù $ r_1, r_2 \dots r_n $ dlouhých $ l_1, l_2 \dots l_n $ +Oznaème si $ l_{max} = \max_{1 \leq i \leq n} l_i $ jako délku nejdel¹ího øetìzce a $R$ jako poèet znakù abecedy. Problém je, ¾e øetìzce nemusí být stejnì dlouhé. S tím se mù¾eme pokusit vypoøádat doplnìním øetìzcù mezerami tak, aby mìly v¹echny stejnou délku, a spustit na nìj algoritmus pro $k$-tice. Tím dostaneme algoritmus, který bude mít èasovou slo¾itost $ \O(l_{max} \cdot n) $, co¾ bohu¾el mù¾e být a¾ kvadratické vzhledem k velikosti vstupu. +Pøíklad: na vstupu mìjme k øetìzcù, kde prvních k-1 z nich bude mít délku 1 a poslední øetìzec bude dlouhý pøesnì k. Vstup má tedy celkovou délku 2k-1 a my teï doplníme prvních k-1 øetìzcù mezerami. Vidíme, ¾e algoritmus teï bude pracovat v èase $ \O(k^2) $. +To, co nám nejvíce zpùsobovalo problémy u pøedchozího pøíkladu bylo velké mno¾ství èasu zabraného porovnáváním doplnìných mezer. Zkusíme proto øe¹it ná¹ problem trochu chytøeji a doplòující mezery do øetìzù vùbec pøidávat nebudeme. +Nejprve roztøídíme zpùsobem podobným Bucket sortu øetìzce do pøihrádek (mno¾in) $ P_i $ podle jejich délek, kde $i$ znaèí délku øetìzcù v dané pøihrádce, neboli definujme $ P_i = \left\{ r_j \| l_j = i \right\} $. Dále si zavedeme seznam setøízených øetìzcù $S$ takový, ¾e v nìm po $k$-tém prùchodu tøídícím cyklem budou øetìzce s délkou alespoò $ l_{max} - k + 1 $ (oznaème $l$) a zároveò v nìm tyto øetìzce budou setøízeny lexikograficky od $l$-tého znaku po $ l_{max} $-tý. Z definice tohoto seznamu je patrné, ¾e po $ l_{max} $ krocích tøídícího cyklu bude tento seznam obsahovat v¹echny øetìzce a tyto øetìzce v nìm budou lexikograficky seøazeny. Zbývá u¾ jen popsat, jak tento cyklus pracuje. Nejprve vezme $l$-tou mno¾inu $ P_l $ a její øetìzce roztøídí do pøihrádek $ Q_j $ (kde index $j$ znaèí j-tý znak abecedy) podle jejich $l$-tého (neboli posledního) znaku. Dále vezme seznam $S$ a jeho øetìzce pøidá opìt podle jejich $l$-tého znaku do stejných pøihrádek $ Q_j $ za ji¾ døíve pøidané øetìzce z $ P_l $. Na závìr postupnì projde v¹echny pøihrádky $ Q_j $ a øetìzce v nich pøesune do seznamu $S$. Proto¾e øetìzce z pøihrádek $ Q_j $ bude brát ve stejném poøadí, v jakém do nich byly umístìny, a proto¾e ze seznamu $S$, který je setøízený podle $ (l + 1) $-ního znaku po $ l_{max} $-tý, bude také brát øetìzce postupnì, bude seznam $S$ po $k$-tém prùchodu pøesnì takový, jaký jsme chtìli (indukcí bychom dokázali, ¾e cyklus pracuje skuteènì správnì). Zároveò z popisu algoritmu je jasné, ¾e bìhem tøídìní ka¾dý znak ka¾dého øetìzce pou¾ijeme právì jednou, tudí¾ algoritmus bude lineární s délkou vstupu. + +Algoritmus: (tøídìní øetìzcù) +\algo +\:$ l_{max} \leftarrow 0 $ +\:Pro $ i \leftarrow 1 $ do $ n $ opakuj: +\::$ l_{max} \leftarrow \max(l_{max}, l_i) $ +\:Pro $ i \leftarrow 1 $ do $ l_{max} $ opakuj: +\::$ P_i \leftarrow \emptyset $ +\::$ p_i \leftarrow 0 $ +\:Pro $ i \leftarrow 1 $ do $ n $ opakuj: +\::$ pridej(P_{l_i}, r_i) $ +\::$ p_i \leftarrow p_i + 1 $ + +\:$ S \leftarrow \emptyset $ +\:$ s \leftarrow 0 $ +\:Pro $ i \leftarrow l_{max} $ do $ 1 $ opakuj: +\::Pro $ j \leftarrow 1 $ do $ R $ opakuj: +\:::$ Q_j \leftarrow \emptyset $ +\:::$ q_j \leftarrow 0 $ + +\::Pro $ j \leftarrow 1 $ do $ p_i $ opakuj: +\:::$ vezmi(P_i, r) $ +\:::$ pridej(Q_{r[i]}, r) $ +\:::$ q_{r[i]} \leftarrow q_{r[i]} + 1 $ +\::Pro $ j \leftarrow 1 $ do $ s $ opakuj: +\:::$ vezmi(S, r) $ +\:::$ pridej(Q_{r[i]}, r) $ +\:::$ q_{r[i]} \leftarrow q_{r[i]} + 1 $ + +\:$ S \leftarrow \emptyset $ +\:$ s \leftarrow 0 $ +\::Pro $ j \leftarrow 1 $ do $ R $ opakuj: +\:::Pro $ k \leftarrow 1 $ do $ q_j $ opakuj: +\::::$ vezmi(Q_j, r) $ +\::::$ pridej(S, r) $ +\::::$ s \leftarrow s + 1 $ + +\:vysledek $S$ +\endalgo -Abychom mohli rychleji hledat - v logaritmickém èase pùlením intervalù. -Pokud chceme zjistit, zda se nìjaké hodnoty opakují, nejde to udìlat lépe ne¾ data setøídít. +Èasová slo¾itost tohoto algoritmu tedy bude $ \O(RN) $, kde $N$ je délka vstupu a $R$ poèet znakù abecedy. \h{Sorting Zoo} @@ -107,6 +149,13 @@ $$ } } $$ + +\h{K èemu je vlastnì tøídìní dobré?} +Díky nìmu mù¾eme rychle vyhledávat prvky v mno¾inì, konkrétnì v èase $ \O(log(n)) $ napø. pomocí pùlení intervalù. +Dal¹ím problémem, na který se hodí pou¾ít tøídìní, je zji¹tìní, zda se v posloupnosti nìjaké její hodnoty opakují. Dá se dokázat, ¾e tuto úlohu nelze vyøe¹it lépe (rychleji), ne¾ hodnoty nejprve setøídit a poté setøizenou posloupnost projít. + +Ukázali jsme si tedy, ¾e v se setøízené mno¾inì jsme schopni vyhledávat prvky v èase $ \O(log(n)) $. Bohu¾el do ní v èase $ \O(log(n)) $ neumíme prvky pøidávat. +Jedním ze zpùsobu, jak zrychlit pøidávání nových prvkù a zároveò nepøijít o logaritmické vyhledávání, je pou¾ít dal¹í datouvou strukturu, vyhledávací stromy. \h{Vyhledávací stromy} Problém: chceme udr¾ovat nìjaká data setøízená. To znamená, ¾e chceme udr¾ovat mno¾inu $X$ prvkù z lineárnì uspoøádaného universa $U$ s operacemi Find (najdi prvek), Insert (vlo¾ prvek), Delete (sma¾ prvek). K tomu se nám bude hodit reprezentace dat pomocí stromu. -- 2.39.2