Matematikailag értem a $ f (n) \ -t O-ban (g (n)) $: $ f (n) $ nem gyorsabban nő, mint $ g (n) $. Formálisabban: $ \ létezik c, n_0 $ s.t. $ f (n) \ leq cg (n) \ összes n \ geq n_0 $.
Hasonlóképpen, a $ f (n) \ in \ Theta (g (n)) $ azt jelenti, hogy a $ f (n) $ hozzávetőlegesen olyan gyorsan növekszik, mint a $ g (n) $. azaz $ f (n) \ O (g (n)), \ Omega (g (n)) $ értékben.
Amit nem értek, az emberek miért használnak nagy Oh-ot a algoritmus? Nem kellene nagy Thetát használni. Amikor egy algoritmus “Futási idejét” mondjuk, akkor a legrosszabb esetre, azaz $ T (n) = max \ {ALG (x): | x | = n \} $.
Tehát, például: a lineáris keresés legrosszabb futási ideje $ n $ méretű bemeneten ($ n $ elem és egy célérték) $ \ Theta (n) $ és $ O (n) $, de a $ \ Theta (n) $ ad további információt. Tehát miért használják az algoritmuskönyvek a $ O (n) $ -ot és nem a $ \ Theta (n) $ -t.
Megjegyzések
- Gyakran ' s, mert egyszerűen ' nem tudunk szoros nagy-thétát kötni egy algoritmus futási idejéhez. Ha egy algoritmus kellően bonyolult, akkor előfordulhat, hogy a legjobbat tehetjük, ha azt mondjuk, hogy a futási idő mondjuk $ O (n ^ {n!}) $, Ahol valójában $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Történelmi okok.
- " Amit nem ' nem értem, hogy az emberek miért használnak nagy Oh-ot egy algoritmus futási idejéhez? Nem kellene, hogy ' t nagy Thetát használjunk. " – Igen. Várjon, ne, még pontosabb kijelentéseket kellene tennünk. De ha választanom kell, akkor igen, $ \ Theta $!
Válasz
Két okot látok, miért az emberek inkább a Big Oh-t részesítik előnyben a Big Theta helyett:
- Egy algoritmus futásidejű bonyolultságát nem feltétlenül a legrosszabb futásidejű bonyolultságként határozzák meg. Lehet, hogy csak futási időnek tekinti egy tetszőleges $ n $ hosszúságú példányon. Ezután, ha azt írja, hogy például egy algoritmus $ t (n) $ futási ideje $ \ mathcal {O} (n ^ 2) $ értékben van, ez azt jelenti, hogy bármilyen $ n $ hosszúságú bemenetet is választ, mindig növekedni fog aszimptotikusan lassabb, mint a $ c \ cdot n ^ 2 $ függvény bizonyos állandó $ c $ értékeknél – ezért nyilvánvalóan kijelentjük a legrosszabb eset futási idejét.
- Néha, amikor elemezzük a futási időt egy olyan algoritmus bonyolultsága, amelyet nem tudsz biztosan tudni, hogy a legrosszabb esetben adott komplexitás valóban szűk-e. Vegyük például a mátrixszorzás futási idejű bonyolultságát . Ott még mindig nem világos, hogy a $ n ^ {2.3728639} $ futási idő valóban a legrosszabb eset-e. És így a futási idő köztudottan $ \ mathcal {O} (n ^ {2.3728639}) $ értékben van, miközben ” s nem biztos benne, hogy a $ \ Theta (n ^ {2.3728639}) $ -ban szerepel-e.
De abban is igazad van, hogy egyes esetekben jobb lenne egy nagy Thétát adni kötött, mint egy nagy Oh kötés.
Megjegyzések
- 1. hirdetés: Olvasók, legyenek óvatosak hogy ne olvasson bele túl sokat !
Válasz
Egy (hanyag) felső határt könnyebb bizonyítani, mint egy szűk felső határt, nem beszélve a felső és alsó határokról.
Néhány algoritmus futási ideje nem tudja em> ugyanolyan funkcióval adható meg, mint a felső / alsó határ. Például. az egyszerű rendezési algoritmusok $ O (n ^ 2) $, de alacsonyabb a $ \ Omega (n) $ korlátja.
Néhányan ragaszkodnak ahhoz, hogy aszimptotikusan teljesítsenek a $ \ sim $ segítségével, ahol $ f (n) \ sim g (n) $ ha
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(mondjuk átlagként, vagy legrosszabb esetben néhány kritikus művelet számát tekintve, például összehasonlítás a válogatás során). Vagyis, vigyázz a szobára, de egyetlen (esetleg humongous) állandó sem söpört a szőnyeg alá.
Megjegyzések
- Amikor a " runtime ", valami olyanra utalunk, mint a legjobb futási idő, a legrosszabb futási idő és az átlagos futási idő. Például: A Quicksort a $ \ Theta (n ^ 2) $ legrosszabb futási idejű, a $ \ Theta (n) $ pedig a legjobb esetben fut. Az aszimptotikumok a jobb függvényeken vannak meghatározva.
Válasz
Ha a big-Theta használható a nagy- Ó, akkor kell használni, hacsak nem okoz szükségtelen megértési nehézségeket. Vannak olyan finom esetek, amikor a big-Theta nem használható a nagy-Oh helyett, például:
Vegye figyelembe a következő problémát: egyenletes hosszúságú tömbök rendezése. A probléma megoldására szolgáló program a következő lehet: ha a tömb hossza páratlan, akkor azonnal lépjen ki, ha a tömb hossza még a buborék rendezése is. Mi ennek az algoritmusnak a legrosszabb esete?
Biztosan $ O (n ^ 2) $, de NEM $ \ Omega (n ^ 2) $ abban az értelemben, hogy $ \ Az Omega $ -ot általában definiálják. Ehelyett a legrosszabb futási ideje a “$ \ Omega (n ^ 2) $ végtelenül gyakran”, úgymond (figyelmeztetés: nem szabványos terminológia).
Válasz
A “Miért használnak algoritmuskönyveket nagy-Oh és nem Theta” válaszban:
Big-Oh a legrosszabb eset elemzésére, a Big-Omega pedig csak a legjobb esetre. De a Big-Theta szempontjából elemezve egyszerre beszélünk mindkét Big-Oh & Big-Omegáról.
azaz. A Big-Theta esetében szükséges, hogy Big-Oh == Big-Omega, különben nem beszélhetünk a Big-Theta-ról.
Tehát ahol valaha (könyv / bármelyik dokumentum) látja a Big-Theta, ők adják a Big-Oh & Big-Omega összetettségét (és mindkettő is egyenlő). De sok esetben nem egyenlőek, akkor csak Big- Ó, csak a legrosszabb esetben.