Zobrazenie zdroja stránky Asymptotické hranice výpočtovej zložitosti

Asymptotická horná a dolná hranica funkcie zložitosti, najlepší, priemerný a najhorší prípad, asymptotická presná notácia.

{{Pojmová mapa}}

Algoritmy, s ktorými sme sa streli v [[Asymptotická notácia|predošlej téme]] mali rôzne hranice ich výpočtových zložitostí. Ale čo to vlastne znamená že tieto funkcie majú určitú hranicu?

Vysvetlime to na jednoduchom kóde:

<syntaxhighlight lang="python3">
# existuje n.index(...), ale to by sme si toho moc neukázali:
def najdi_index_prvku(zoznam, hladaj):
  for n, prvok in enumerate(zoznam): # n = index aktuálneho prvku
    if prvok == hladaj:
      return n

  return -1 # prvok sa nenašiel
</syntaxhighlight>

Časová zložitosť tohto algoritmu je <math>O(n)</math> (lineárna), priestorová <math>O(1)</math> (konštantná – nepoužíva dodatočnú pamäť).

Keďže zoznam na vstupe je usporiadanou množinou, môže nastať viacero situácií. Napríklad:

<syntaxhighlight lang="python3">
zoznam = [1, 2, 3]

hladaj = 4
index = najdi_index_prvku(zoznam, hladaj)
print(index) # vypíše -1
# prvok neexistuje, musíme teda prejsť celým zoznamom
# časová zložitosť je preto O(n)
# (ak predpokladáme, že prvok sa nikdy nebude v zozname nachádzať = najhorší prípad)

hladaj = 1
index = najdi_index_prvku(zoznam, hladaj)
print(index) # vypíše 0
# číslo 1 sa nachádza na prvom indexe (0), čo predstavuje najlepší (ideálny) prípad
# ak by sa hľadaný prvok vždy nachádzal na prvom mieste
# (teda, vždy by sme mali ideálne podmienky a najlepší prípad), tak by zložitosť bola
# konštantná = O(1), pretože by sme vykonali iba jednu operáciu porovnania
</syntaxhighlight>

Vidíme dva prípady:

* V prvom je časová zložitosť <math>O(n)</math>, pretože '''musíme prejsť všetkými prvkami v zozname''' – a nakoniec zistíme, že sa tam prvok aj tak '''nenachádza'''.
** Toto sa nazýva: '''najhorší prípad''';
** Vyjadruje ju notácia ''<u>Big-O</u>'': <math>O(f(n))</math>;
* V druhom prípade je časová zložitosť <math>O(1)</math>, pretože '''hľadaný prvok sa nachádza na prvom mieste''', vykonáme teda '''iba jednu operáciu''' porovnania (a zložitosť je konštantná).
** Toto sa nazýva: '''najlepší prípad''';
** Vyjadruje ju notácia ''<u>Omega</u>'': <math>\Omega(f(n))</math>;
* ''Poznámka:'' v oboch prípadoch je priestorová zložitosť <math>O(1)</math>, pretože samotný algoritmus nepotrebuje žiadnu dodatočnú pamäť ktorá by sa menila v závislosti od <math>n</math>.

Z toho vyplýva, že v závislosti od usporiadania prvkov na vstupe a hodnoty ktorú hľadáme sa môže zmeniť aj výpočtová zložitosť algoritmu. Avšak, v praxi sme pesimisti a najčastejšie vždy vyjadrujeme Big-O notáciu (teda, <math>O(f(n))</math>), pretože predpokladáme Murphyho zákon, teda:

<blockquote>Všetko čo sa môže pokaziť, sa pokazí.</blockquote>

Asi si vieš predstaviť, že to tak naozaj funguje. Ale niekedy je možno užitočné vyjadriť aj '''priemerný prípad''' – je to v podstate spojenie hornej a dolnej hranice funkcie výpočtovej zložitosti, a vyjadrujeme ju ako Theta: <math>\Theta(f(n))</math>. Theta notáciu môžeme použiť iba vtedy, ak vieme že '''priemerná zložitosť je presne ohraničená zhora aj zdola rovnakou funkciou'''.

V skratke:

* Ak '''vieme len hornú hranicu''', ale nie dolnú, použijeme '''Big-O''' notáciu;
* Ak '''vieme len dolnú hranicu''', ale nie hornú, použijeme '''Omega''' notáciu;
* Ak je rast výpočtovej zložitosti algoritmu presne '''obmedzený rovnakou funkciou zhora aj zdola''', použijeme '''Theta''' notáciu;

== Najhorší prípad ==
.

== Najlepší prípad ==
.

== Priemerný prípad ==
Existuje aj algoritmus, ktorý dokáže obsiahnuť všetky príklady:

<syntaxhighlight lang="python3">
def spocitaj_prvky(mnozina):
  pocet = 0

  for _ in mnozina:
    pocet += 1

  return pocet
</syntaxhighlight>

V tomto algoritme je najhorší prípad zároveň aj najlepším. Bez ohľadu na veľkosť alebo usporiadanie prvkov v poli musíme vždy prejsť všetkými prvkami. Preto sú všetky notácie časovej zložitosti lineárne:

* pre hornú (Big-O) hranicu: <math>O(n)</math>;
* pre dolnú (Omega) hranicu: <math>\Omega(n)</math>;
* pre priemernú (Theta) hranicu: spojenie hornej a dolnej hranice, v podstate stále iba <math>\Theta(n)</math>;
Ale formálne môžme uviesť iba priemerný prípad (Theta notáciu), teda <math>\Theta(n)</math>.

bubblesort test iframe

<iframe allowtransparency="true" src="http://coding.poznamkovac.eu/#/embed/custom?data=eyJ0aXRsZSI6IkJ1YmJsZSBTb3J0IiwiYXNzaWdubWVudCI6IjxwPk5hcHJvZ3JhbXVqIGFsZ29yaXRtdXMgQnViYmxlIFNvcnQgdiBKYXZhU2NyaXB0ZS48L3A-XG48cD5Bcmd1bWVudCA8Y29kZT5qZVZ6b3N0dXBuZTwvY29kZT4ga29udHJvbHVqZSwgxI1pIHNhIG3DoSBwb2xlIHpvcmFkacWlIHZ6b3N0dXBuZSBhbGVibyBuaWUgKG3DtMW-ZSBiecWlIDxjb2RlPnRydWU8L2NvZGU-IHByZSB6b3JhZGVuaWUgb2QgbmFqbWVuxaFpZWhvIHBvIG5hanbDpMSNxaHDrSBhbGVibyA8Y29kZT5mYWxzZTwvY29kZT4gcHJlIHpvcmFkZW5pZSBvZCBuYWp2w6TEjcWhaWVobyBwbyBuYWptZW7FocOtKS48L3A-IiwibWF4U2NvcmUiOjIsImZpbGVzIjpbeyJmaWxlbmFtZSI6ImluZGV4Lmh0bWwiLCJyZWFkb25seSI6ZmFsc2UsImhpZGRlbiI6dHJ1ZSwiYXV0b3JlbG9hZCI6ZmFsc2UsImNvbnRlbnQiOiI8IURPQ1RZUEUgaHRtbD5cbjxodG1sPlxuPGhlYWQ-XG4gIDxtZXRhIGNoYXJzZXQ9XCJVVEYtOFwiPlxuICA8dGl0bGU-QnViYmxlIFNvcnQ8L3RpdGxlPlxuICA8bGluayByZWw9XCJzdHlsZXNoZWV0XCIgaHJlZj1cInN0eWxlLmNzc1wiPlxuPC9oZWFkPlxuPGJvZHk-XG4gIDxzY3JpcHQgc3JjPVwic2NyaXB0LmpzXCI-PC9zY3JpcHQ-XG48L2JvZHk-XG48L2h0bWw-In0seyJmaWxlbmFtZSI6InNjcmlwdC5qcyIsInJlYWRvbmx5IjpmYWxzZSwiaGlkZGVuIjpmYWxzZSwiYXV0b3JlbG9hZCI6dHJ1ZSwiY29udGVudCI6ImZ1bmN0aW9uIGJ1YmJsZVNvcnQocG9sZSwgamVWem9zdHVwbmU9ZmFsc2UpIHtcbiAgLy8gYnViYmxlIHNvcnRcblxuICByZXR1cm4gcG9sZTtcbn0ifSx7ImZpbGVuYW1lIjoidGVzdC5qcyIsInJlYWRvbmx5IjpmYWxzZSwiaGlkZGVuIjp0cnVlLCJhdXRvcmVsb2FkIjpmYWxzZSwiY29udGVudCI6ImZ1bmN0aW9uIHJ1blRlc3RzKHdpbmRvdykge1xuICBmdW5jdGlvbiBjb3JyZWN0QnViYmxlU29ydChwb2xlLCBqZVZ6b3N0dXBuZSA9IGZhbHNlKSB7XG4gIGZvciAobGV0IGkgPSAwOyBpIDwgcG9sZS5sZW5ndGg7IGkrKykge1xuICAgIGZvciAobGV0IGogPSAwOyBqIDwgcG9sZS5sZW5ndGggLSBpIC0gMTsgaisrKSB7XG4gICAgICBpZiAoamVWem9zdHVwbmUpIHtcbiAgICAgICAgaWYgKHBvbGVbal0gPCBwb2xlW2ogKyAxXSkge1xuICAgICAgICAgIGxldCBwb20gPSBwb2xlW2pdO1xuICAgICAgICAgIHBvbGVbal0gPSBwb2xlW2ogKyAxXTtcbiAgICAgICAgICBwb2xlW2ogKyAxXSA9IHBvbTtcbiAgICAgICAgfVxuICAgICAgfSBlbHNlIHtcbiAgICAgICAgaWYgKHBvbGVbal0gPiBwb2xlW2ogKyAxXSkge1xuICAgICAgICAgIGxldCBwb20gPSBwb2xlW2pdO1xuICAgICAgICAgIHBvbGVbal0gPSBwb2xlW2ogKyAxXTtcbiAgICAgICAgICBwb2xlW2ogKyAxXSA9IHBvbTtcbiAgICAgICAgfVxuICAgICAgfVxuICAgIH1cbiAgfVxuICByZXR1cm4gcG9sZTtcbn1cblxuICBjb25zdCB0ZXN0cyA9IFtcbiAgICB7XG4gICAgICBuYW1lOiBcIkJ1YmJsZSBzb3J0IHpvc3R1cG5lXCIsXG4gICAgICB0ZXN0OiBmdW5jdGlvbih3aW5kb3cpIHtcbiAgICAgICAgbGV0IGFycmF5ID0gWy0xMiwgMCwgNSwgLTgsIDUsIDMsIDIsIDEsIDksIDEwLCA1MF07XG4gICAgICAgIC8vIFNvcnRlZCBkZXNjZW5kaW5nIG9yZGVyLlxuICAgICAgICBsZXQgYSA9IGNvcnJlY3RCdWJibGVTb3J0KGFycmF5LnNsaWNlKCksIHRydWUpO1xuICAgICAgICBsZXQgYiA9IHdpbmRvdy5idWJibGVTb3J0KGFycmF5LnNsaWNlKCksIHRydWUpO1xuICAgICAgICBsZXQgc3VjY2VzcyA9IEpTT04uc3RyaW5naWZ5KGEpID09PSBKU09OLnN0cmluZ2lmeShiKTtcbiAgICAgICAgcmV0dXJuIHsgXG4gICAgICAgICAgc3VjY2VzcyxcbiAgICAgICAgICBtZXNzYWdlOiBzdWNjZXNzID8gXCLEjMOtc2xhIHPDuiB6b3JhZGVuw6lcIiA6IFwixIzDrXNsYSBuaWUgc8O6IHpvcmFkZW7DqVwiIFxuICAgICAgICB9O1xuICAgICAgfVxuICAgIH0sXG4gICAge1xuICAgICAgbmFtZTogXCJCdWJibGUgc29ydCB2em9zdHVwbmVcIixcbiAgICAgIHRlc3Q6IGZ1bmN0aW9uKHdpbmRvdykge1xuICAgICAgICBsZXQgYXJyYXkgPSBbLTEyLCAwLCA1LCAtOCwgNSwgMywgMiwgMSwgOSwgMTAsIDUwXTtcbiAgICAgICAgLy8gU29ydGVkIGFzY2VuZGluZyBvcmRlci5cbiAgICAgICAgbGV0IGEgPSBjb3JyZWN0QnViYmxlU29ydChhcnJheS5zbGljZSgpLCBmYWxzZSk7XG4gICAgICAgIGxldCBiID0gd2luZG93LmJ1YmJsZVNvcnQoYXJyYXkuc2xpY2UoKSwgZmFsc2UpO1xuICAgICAgICBsZXQgc3VjY2VzcyA9IEpTT04uc3RyaW5naWZ5KGEpID09PSBKU09OLnN0cmluZ2lmeShiKTtcbiAgICAgICAgcmV0dXJuIHsgXG4gICAgICAgICAgc3VjY2VzcyxcbiAgICAgICAgICBtZXNzYWdlOiBzdWNjZXNzID8gXCLEjMOtc2xhIHPDuiB6b3JhZGVuw6lcIiA6IFwixIzDrXNsYSBuaWUgc8O6IHpvcmFkZW7DqVwiIFxuICAgICAgICB9O1xuICAgICAgfVxuICAgIH1cbiAgXTtcbiAgXG4gIHJldHVybiB0ZXN0cy5tYXAodCA9PiB7XG4gICAgY29uc3QgcmVzdWx0ID0gdC50ZXN0KHdpbmRvdyk7XG4gICAgcmV0dXJuIHtcbiAgICAgIG5hbWU6IHQubmFtZSxcbiAgICAgIHN1Y2Nlc3M6IHJlc3VsdC5zdWNjZXNzLFxuICAgICAgbWVzc2FnZTogcmVzdWx0Lm1lc3NhZ2VcbiAgICB9O1xuICB9KTtcbn1cbiJ9XSwibWFpbkZpbGUiOiJpbmRleC5odG1sIiwicHJldmlld1R5cGUiOiJodG1sIn0&showPreview=false" style="width: 100%; height: 850px; border: none; background: transparent;"></iframe>

{{Téma|Oblast=Kategória:Algoritmy a výpočtová zložitosť|Poradie=40}}

[[Kategória:Algoritmy a výpočtová zložitosť]]