Milyen bonyolultsági osztályba tartozik ez az algoritmus?

O(f(n))-nek azok az elemei, amikhez tudunk találni olyan c konstans számot, hogy egyik elem se érje el c*f(n)-t, ahogy az n növekszik egy rögzített n0 után. Tehát f(n)-t fel tudod rajzolni úgy a grafikonra tetszőlegesen eltolva az y-n tengelyen, hogy akármilyen összehasonlítást végzel, ezt az értéket ne érje el. Neked komplexitás becslése során egy ilyen "maximumot" (idézőjel!) kell keresned. O(m) nem azt mondja, hogy m összehasonlítást kell végezned, hanem azt, hogy akármekkorák a stringek, egyik sem lesz költségesebb mint c*m.

Ne keverd össze az "alsó becsléssel', ami az omega, vagy a kétoldalival, ami a teta.

"A rendezés pedig szerinte akkor lenne n*logn ha minden string 1 karakter hosszú lenne hiszen stringeket karakterenként hasonlítunk össze és nem mindegy hogy 1 karakter hosszú stringeket hasonlítunk össze vagy 1 millió karakter hosszúakat."

LOL

A rendezés ABC szerint kelene, hogy végbemenjen, akkor mi a bánatnak kéne végigmenni a string minden egyes karakterén?

Azt nem tudhatjuk előre, hogy a stringek tartalma mi, tehát ennek a feladatnak az Ordóját ennyi infóból lehetetlen megállapítani.

14-es tegyük fel ez a két stringed:

"aaaaaaaaaaaaarwetedfcvbtzrknmsd"

"aaaaaaaaaaaabedfaskdfvsefiburelnikaveldexarte"

Hány karakteren mész végig hogy összehasonlítsd?

Mert ha az egészen, akkor meg is érdemled.

Megismétlem:

Azt nem tudhatjuk előre, hogy a stringek tartalma mi, tehát ennek a feladatnak az Ordóját ennyi infóból lehetetlen megállapítani.

"Osztálytársam azt mondja hogy az első lépés attól függ hogy milyen nyelvről beszélünk mert ha mutable a string"

Az osztálytársad inkjább még tanulgasson.

A komplexnél az egész feladatot vesszük, nem azt, hogy ekkor vagy akkor mi van.

Ha a válaszott eszköz (nyelv) igényel cserét, akkor a csere is a feladat része lesz, tehát a komplexre is hatással lesz.