Futásidő komplexitás legrosszabb eset?

"A hasító táblába az a jó, hogy O(1) a keresési ideje egyszeri keresésre akármekkora az adathalmaz, de ez csak ideális esetben. Legrosszabb esetben O(n)."

Elolvastad a 16-os kommentet? Idezem:

"ha binary tree alapu a hash bucket implementacio"

Lancolt listas implementacional lenne O(n).

Illetve zarojelben meg, a quicksort nem O(n^2) median of medians pivot valasztassal, hanem n*logn. Csak mivel a konstans faktor miatt sok esetben lassabb, mint a random pivot, igy nem hasznaljak gyakorlatban.

"Illetve zarojelben meg, a quicksort nem O(n^2) median of medians pivot valasztassal, hanem n*logn. Csak mivel a konstans faktor miatt sok esetben lassabb, mint a random pivot, igy nem hasznaljak gyakorlatban."

Legrosszabb esetről beszéltünk, egyetemi anyag is egyébként, de a wiki is írja : [link] ( Worst-case O(n^2) ).

Írtam az AVL fát is meg a hasítótáblát is melyikben mennyi. Egybéként ha már így belemegyünk : [link]

[link]

Ok, akkor linkelek en is wiki-t:

[link]

Meg be is idezem neked, amit leirtam:

Median of medians can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(nlog n). Although this approach optimizes the asymptotic worst-case complexity quite well, it is typically outperformed in practice by instead choosing random pivots for its average O(n) complexity for selection and average O(nlog n) complexity for sorting, without any overhead of computing the pivot.

(Mellesleg jobb egyetemeken ez is tananyag)

"20-as megkérdeztem egyetemi matek tanárt is azóta és jó a log(n!)."

Az oké, csak kérdés hogy egyről beszélünk e meg ő is arra gondolt meg azt közölted e vele mint itt. Azaz mi a specifikáció melynek annyi az időkomplexitása.

"Mellesleg jobb egyetemeken ez is tananyag"

Az is igaz, az sose négyzetes idejű, de én a quicksort-ra reflektáltam rendezési algoritmus szempontjából, az is írja rá a négyzetes időt (legrosszabb esetben a quicksort-ra).