Futásidő komplexitás legrosszabb eset?

"Megtettem 10000 elemre 900 ms körül fut."

lol

A komplexitás egy algoritmus minden egyes műveletének elvégzéséhez szükséges időigényt /time/ és tárigényt /space/ kifejező számérték a pozitív egész számok halmazán.

Kicsit el vagy tevedve #15. A Cornell egyetemnek van egy jo irasa az aszimptotikus komplexitasrol, erdemes elolvasnod:

[link]

"5-ös a HashSet megoldásnál akkor n*logn a legrosszabb eset?"

Nem, O(log(n!)) a legrosszabb eset, ha binary tree alapu a hash bucket implementacio es konstans a hash fuggveny komplexitasa.

Legyen ez az implementacio, csak, hogy egyertelmu legyen mirol beszelek:

[link]

A legrosszabb esetben ugye nincs ket egyenlo elem a tombben es minden elem ugyanahhoz az ertekhez hashel. Ekkor n elem beszurasa a setbe 1db n elemu (balanced) binary treet eredmenyez.

(A masik kerdesnel aki az O(n*logn) komplexitast irta, o valoszinuleg ugy szamolt, hogy minden elemnel ezzel az n elemu treevel dolgozunk, de nyilvan nem ez a helyzet)

Elkezdunk iteralni a tombon, az elso elemnel meg ures a set, a masodik elemnel 1 elem van a setben, a harmadik elemnel 2 elem van a setben, a negyedik elemnel 3 es igy tovabb, az n-edik elemnel n-1 elem van a setben.

Elhagyjuk a konstans faktort, igy nez ki a dolog:

log(n-1)+log(n-2)+log(n-3)+log(n-4)+...+log(1)

Asszem kozepiskolai tananyag a logaritmus azonossagok, log(a)+log(b)=log(ab), igy ez egyenlo a kovetkezovel:

log((n-1)(n-2)(n-3)(n-4)...(1))

A kulso zarojelben levo kifejezes nyilvan n-1 faktorialis, igy O(log(n!)) a time complexity. A space O(n).

Ne köszönd mert rossz a válasz.

"Elhagyjuk a konstans faktort, igy nez ki a dolog:

log(n-1)+log(n-2)+log(n-3)+log(n-4)+...+log(1)"

Legrosszabb esetben nem logaritmikus lesz,hanem lineáris idejű egy keresés hasító táblában, de mivel nem egy keresést hajtunk végre, hanem n darabot így a futási idő legrosszabb esetben ha már így kifejtjük akkor első n szám összege: n+(n-1)+(n-2)+...+1 = n^2 vagyis O(n^2) legrosszabb esetben.

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). Amit a másik kérdésnél ír a 7-es a gyorsrendezésre (quicksort) az se igaz, az is legrosszabb esetben O(n^2) időkomplexitású. Az AVL-tree az O(log(n)) keresési idejű legrosszabb esetben is, így a kérdéses feladatra O(n*log(n)) legrosszabb esetben (is).