Algorytmy i struktury danych 1 - Wykład 4 PDF

Algorytmy i struktury danych 1 Wykład 4 Slajdy napisane przez mgr inż. Patryk Mendoń [email protected] Zaktualizowane przez Dr. Gleb Polevoy, Prof. UO [email protected] Drzewo decyzyjne Graficzna metoda przedstawiania...

Algorytmy i struktury danych 1 Wykład 4 Slajdy napisane przez mgr inż. Patryk Mendoń [email protected] Zaktualizowane przez Dr. Gleb Polevoy, Prof. UO [email protected] Drzewo decyzyjne Graficzna metoda przedstawiania procesu decyzyjnego. Sortowanie za pomocą porównań Który kierunek oznacza „tak”?  Sortowanie za pomocą porównań Drzewo decyzyjne o m liściach ma wysokość co najmniej log m. W prostym dowodzie pokazuje się najpierw indukcyjnie, że drzewo binarne o wysokości h ma co najwyżej 2h liści. Drzewo decyzyjne algorytmu sortującego n elementów ma co najmniej n! liści. Każdy algorytm sortujący za pomocą porównań wykonuje co najmniej c nlog n porównań dla ciągu n-elementowego, bo 𝑛 𝑛 𝑛 l𝑜𝑔 𝑛! = σ𝑛𝑖=1 log 𝑖 ≥ log = log 𝑛 − 1 =Ω(n log(n)) 2 2 2 Już wiemy, że można osiągnąć θ(n log(n)) Dziel i zwyciężaj Sortowanie przez scalanie Łącz nie jest in-place! Sortowanie przez scalanie Sortowanie przez scalanie Sortowanie przez scalanie - pseudokod Złożoność czasowa algorytmu sortowania przez scalanie Rozwiązywanie równań rekurencyjnych Rekurencja liniowa (ze stałymi współczynnikami)  Jednorodna (zerowy dodatkowy termin) rekurencja liniowa  Niejednorodna rekurencja liniowa Rekurencja typu „dziel i zwyciężaj” Rekurencja typu „jeden krok w tył” Jednorodna rekurencja liniowa Jednorodne równanie liniowe ze stałymi współczynnikami: Ogólne rozwiązanie rekurencji Jednorodna rekurencja liniowa Przykład jednorodnej rekurencji liniowej Write the run-time recursion  Przykład obliczania złożoności jednorodnej rekurencji liniowej Tu mamy: Rekurencja typu „dziel i rządź” Rekurencja tego typu dotyczy problemów o rozmiarze n, które możemy podzielić na a podproblemów, każdy o rozmiarze n/b. Równanie rekurencyjne ma postać: Czy to jest szczególny przypadek rekurencji liniowej? dla n>1 i n będącego potęgą b, b≥2 i b N, k≥0 i k N, a>0, c>0, d≥0 Rekurencja typu „dziel i rządź” Wpisz tutaj równanie. Dla każdego 𝑗 ≤ 𝑘, 𝑔𝑑𝑧𝑖𝑒 𝑘 = log 𝑏 𝑛 Rekurencja typu „dziel i rządź” Przykład rekurencji typu „dziel i rządź” Write the run-time recursion Przykład obliczania złożoności rekurencji typu „dziel i rządź” Porównanie złożoności czasowej algorytmów sortujących Algorytm Optymistyczna złożoność Pesymistyczna złożoność czasowa czasowa Sortowanie przez scalanie O(𝑛 log 𝑛) O(𝑛 log 𝑛) Sortowanie przez kopcowanie O(𝑛 log 𝑛) O(𝑛 log 𝑛) Szybkie sortowanie O(𝑛 log 𝑛) O(𝑛2) Sortowanie bąbelkowe O(𝑛) O(𝑛2) Sortowanie przez wstawianie O(𝑛) O(𝑛2) Sortowanie przez wybieranie O(𝑛2) O(𝑛2) Porównanie złożoności obliczeniowej algorytmów sortujących