Jól értem a műveletigényt?

"Szóval ha az a feladat, hogy számoljuk ki a legrosszabb futásidőt, akkor csak annyi az Ordó, hogy odaírom a számolás végére, hogy O(n^2) például (ha n^2-es a futásidő)? Tehát azt nem nekem kell kitalálnom, hogy amit számoltam az Ordó, Théta vagy Omega-e?"

Nyilvan tudnod kell, hogy mit szamolsz, kulonben nem tudnad kiszamolni. Azt irod a szamolas vegere, amit szamoltal.

Azert, mert ha azt mondod, hogy a legrosszabb eset muveletigenye, akkor nincs definialva sem a legrosszabb eset, sem a muveletigeny.

Ha azt mondod, hogy nagy ordo, akkor egyertelmu, hogy aszimptotikus komplexitasrol van szo es elhagyhato pl. a konstans faktor, ami elobbibol nem derul ki.

Nem, nem érted jól. f = O(g) azt jelenti, hogy elég nagy n-re f felvett értékei kisebbek g értékeinek valahányszorosainál. A jelölés akkor alkalmazható, ha egy függvény pontos értékére nem vagyunk kíváncsiak, csak nagyságrendjére (illetve annak felső korlátjára). Például ha f(n) = (3/2)n^2 + (5/6)n + 42, akkor megtehetjük, hogy csak annyit adunk meg, hogy O(n^2).

Ennek idáig nincs köze algoritmusokhoz. Nem lehet úgy defniálni hogy "legrosszabb esetének műveletigénye", mert f és g mezei függvények, nincs sem legrosszabb esetük, sem műveletigényük.

Amúgy de, neked kéne kitalálnod, hogy a három jelölés közül melyiket kell alkalmazni, de ha ennyire nem érted a definíciókat, akkor ez nem fog menni. Írj mindig ordót, az a ZH-feladatok 80%-ában helyes lesz.

Nincs logikai megfeleltetés a három műveletigény és a három jelölés között, csak annyi, hogy tipikusan melyiknél melyiket alkalmazzuk. Nincs olyan szabály, hogy az egyiknél csak egyiket alkalmazhatjuk.

Például kupacrendezésnél először megállapítjuk, hogy egy n*log n nagyságrendű függvény felső korlátja a legrosszabb költségnek, ezt O-val vonatkoztathatjuk a költségre, vagyis azt írjuk fel (MT(n)-nel jelölöm a legrosszabb költséget), hogy MT(n) = O(n*log(n)). Egy másik gondolat mutatja, hogy egy szintén n*log(n) nagyságrendű függvény alsó korlátja a műveletigénynek; ezúttal azt kell írnom, hogy MT(n) = Ω(n*log(n)). Elő is állt egy helyzet, amelyben Ω-jelölést alkalmazunk, pedig még mindig a legrosszabb költségről van szó. A kettőt összevonva írhatom a végeredményt, miszerint MT(n) = Θ(n*log(n)), így már mindhárom jelölést alkalmaztam ugyanarra a költségfogalomra és haszna is volt: több információt nyertünk az algoritmusról.

Valóban az Ordó hordozza az információ lényegét legrosszabb esetben, ettől még logikailag felírhatunk összefüggést a másik két jelöléssel is, sőt időnként fontos is mint a példa mutatja.