logo

Pokročilá hlavní věta pro opakování rozděl a panuj

Master Theorem je nástroj používaný k řešení rekurentních vztahů, které vznikají při analýze algoritmů rozděl a panuj. Master Theorem poskytuje systematický způsob řešení rekurentních vztahů ve tvaru:

T(n) = aT(n/b) + f(n)



  1. kde a, b a f(n) jsou kladné funkce a n je velikost problému. Hlavní věta poskytuje podmínky, aby řešení recidivy bylo ve tvaru O(n^k) pro nějakou konstantu k, a dává vzorec pro určení hodnoty k.
  2. Pokročilá verze Master Theorem poskytuje obecnější formu věty, která dokáže zpracovat rekurentní vztahy, které jsou složitější než základní forma. Pokročilá verze Master Theorem zvládne opakování s více termíny a složitějšími funkcemi.
  3. Je důležité poznamenat, že hlavní věta není použitelná pro všechny recidivy a nemusí vždy poskytnout přesné řešení dané recidivy. Je to však užitečný nástroj pro analýzu časové složitosti algoritmů rozděl a panuj a poskytuje dobrý výchozí bod pro řešení složitějších recidiv.

Master Theorem se používá k určení doby běhu algoritmů (algoritmů rozděl a panuj) z hlediska asymptotických zápisů.
Zvažte problém, který je vyřešen pomocí rekurze.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

Výše uvedený algoritmus rozděluje problém na A podproblémy, každý o velikosti n/b, a rekurzivně je řešit, aby se vypočítal problém a práce navíc, která byla pro problém vykonána, je dána f(n), tj. časem na vytvoření podproblémů a zkombinování jejich výsledků ve výše uvedené proceduře.

Takže podle hlavního teorému lze dobu běhu výše uvedeného algoritmu vyjádřit jako:



 T(n) = aT(n/b) + f(n)>

kde n = velikost problému
a = počet dílčích problémů v rekurzi a a>= 1
n/b = velikost každého dílčího problému
f(n) = náklady na práci provedenou mimo rekurzivní volání, jako je rozdělení na dílčí problémy a náklady na jejich kombinování za účelem získání řešení.

Ne všechny rekurentní vztahy lze vyřešit pomocí hlavní věty, tj

  • T(n) není monotónní, např.: T(n) = sin n
  • f(n) není polynom, např.: T(n) = 2T(n/2) + 2n

Tato věta je pokročilou verzí hlavní věty, kterou lze použít k určení doby běhu algoritmů rozděl a panuj, pokud má opakování následující formu: -



Vzorec pro výpočet doby běhu algoritmů rozděl a panuj

kde n = velikost problému
a = počet dílčích problémů v rekurzi a a>= 1
n/b = velikost každého dílčího problému
b> 1, k>= 0 a p je reálné číslo.

Pak,

  1. pokud a> bk, pak T(n) = θ(nlogbA)
  2. pokud a = bk, pak
    (a) pokud p> -1, pak T(n) = θ(nlogbAlogp+1n)
    (b) jestliže p = -1, pak T(n) = θ(nlogbAloglogn)
    (c) jestliže p <-1, pak T(n) = θ(nlogbA)
  3. Pokud k, tedy
    (a) jestliže p>= 0, pak T(n) = θ(nklogpn)
    (b) jestliže p <0, pak T(n) = θ(nk)

Analýza časové složitosti –

    Příklad-1: Binární vyhledávání – T(n) = T(n/2) + O(1)
    a = 1, b = 2, k = 0 a p = 0
    bk= 1. Takže a = bka p> -1 [Případ 2.(a)]
    T(n) = θ(nlogbAlogp+1n)
    T(n) = θ(logn) Příklad-2: Sloučit řazení – T(n) = 2T(n/2) + O(n)
    a = 2, b = 2, k = 1, p = 0
    bk= 2. Takže a = bka p> -1 [Případ 2.(a)]
    T(n) = θ(nlogbAlogp+1n)
    T(n) = θ(nlogn) Příklad-3: T(n) = 3T(n/2) + n2
    a = 3, b = 2, k = 2, p = 0
    bk= 4. Takže, a k a p = 0 [Případ 3.(a)]
    T(n) = θ(nklogpn)
    T(n) = θ(n2)

    Příklad-4: T(n) = 3T(n/2) + log2n
    a = 3, b = 2, k = 0, p = 2
    bk= 1. Takže a> bk[Případ 1]
    T(n) = θ(nlogbA)
    T(n) = θ(nlog23)

    Příklad-5: T(n) = 2T(n/2) + nlog2n
    a = 2, b = 2, k = 1, p = 2
    bk= 2. Takže a = bk[Případ 2.(a)]
    T(n) = θ(nlogbAlogp+1n)
    T(n) = θ(nlog22log3n)
    T(n) = θ(nlog3n)

    Příklad-6: T(n) = 2nT(n/2) + nn
    Toto opakování nelze vyřešit pomocí výše uvedené metody, protože funkce není ve tvaru T(n) = aT(n/b) + θ(nklogpn)

GATE Cvičné otázky –

  • GATE-CS-2017 (Sada 2) | Otázka 56
  • GATE IT 2008 | Otázka 42
  • GATE CS 2009 | Otázka 35

Zde je několik důležitých bodů, které je třeba mít na paměti ohledně Master Theorem:

  1. Opakování rozděl a panuj: Hlavní teorém je speciálně navržen k řešení vztahů opakování, které vznikají při analýze algoritmů rozděl a panuj.
  2. Forma rekurence: Hlavní věta platí pro rekurentní vztahy ve tvaru T(n) = aT(n/b) + f(n), kde a, b a f(n) jsou kladné funkce a n je velikost problému.
  3. Časová složitost: Master Theorem poskytuje podmínky pro řešení rekurence ve tvaru O(n^k) pro nějakou konstantu k a dává vzorec pro určení hodnoty k.
  4. Pokročilá verze: Pokročilá verze Master Theorem poskytuje obecnější formu věty, která dokáže zpracovat rekurentní vztahy, které jsou složitější než základní forma.
  5. Omezení: Hlavní věta není použitelná pro všechny recidivy a nemusí vždy poskytovat přesné řešení dané recidivy.
  6. Užitečný nástroj: Přes svá omezení je Master Theorem užitečným nástrojem pro analýzu časové složitosti algoritmů rozděl a panuj a poskytuje dobrý výchozí bod pro řešení složitějších recidiv.
  7. Doplněno o další techniky: V některých případech může být nutné doplnit Master Theorem o další techniky, jako je substituční metoda nebo iterační metoda, aby se zcela vyřešil daný rekurentní vztah.