A legjobb és a rosszabb eset bemenetei a halom és gyors rendezéshez?

kupac- Mivel a legjobb és a legrosszabb eset ugyanaz nem számít a beviteli sorrend? Az összehasonlítások és a hozzárendelések száma mindig megegyezik? Úgy gondolom, egy halom rendezésben ugyanez lehet, mivel a valódi munka a beillesztésben történik, de a rendezés csak a max / perc halom? Ezért van az?

A ténylegesen elvégzett összehasonlítások száma függhet az értékek megadásának sorrendje. Az a tény, hogy a legjobb és a legrosszabb eset mindegyik Θ (n log n) – feltéve, hogy minden elem megkülönböztethető – csak azt jelenti, hogy aszimptotikusan nincs különbség a kettő között, bár állandó tényezővel különbözhetnek egymástól. Erre nincs egyszerű példa a fejem tetejére, de úgy gondolom, hogy létrehozhat olyan bemeneteket, ahol az összehasonlítások száma állandó tényezővel különbözik a két megközelítés. Mivel a big-O jelölés figyelmen kívül hagyja az állandókat, ez nem tükröződik a legjobb és a legrosszabb eset elemzésében.

gyors rendezés – ez Nem tudom biztosan. Nem vagyok biztos benne, mi a legjobb és a legrosszabb eset. Ha például egy már 10 karakterláncból álló válogatott lista nem lenne szükséges, akkor mindig ugyanannyi pivot kell választanunk a rekurzív algoritmus teljesítéséhez? A magyarázat bármilyen segítsége valóban segítene.

A kiválasztott pivotok száma valóban megegyezik az algoritmus végrehajtásától függetlenül. A forgásonként elvégzett munka azonban attól függően változhat, hogy milyen osztásokat kap. A legjobb esetben az egyes lépésekben kiválasztott forgócsap a tömb középső eleme lesz. Amikor ez megtörténik, (nagyjából) n összehasonlítást hajtunk végre a rekurzió felső rétegén, majd (nagyjából) n a következő rétegnél, mert két n / 2 méretű alsáv található, majd a következőnél (nagyjából) n van. réteg, mert négy n / 4 méretű alsáv van, stb. Mivel vannak Θ (log n) rétegek, és mindegyik réteg Θ n) munka, az összes elvégzett munka Θ (n log n). Másrészt fontolja meg az egyes tömbök abszolút minimumának kiválasztását pivotként. Ezután (nagyjából) n összehasonlítást végeznek a felső rétegben, majd (nagyjából) n – 1 a következő rétegben, majd (nagyjából) n – 2 a következő rétegben stb. Az összeg 1 + 2 + 3 + … + n Θ (n ² ), tehát a legrosszabb eset is.

Remélem, ez segít!

Hozzászólások

• Uram, hogy van a legjobb esetben a heapsort nlogn? Ha úgy gondoljuk, hogy az összes elem azonos, akkor a költség csak a tömb összes elemét iterálja, és nem mozdul el a gyökérig. Tehát szerintem omega (n) legyen.
• Ez jó pont. Különálló elemeket feltételeztem, ezért frissítem ezt a választ.

Mivel senki sem valóban címzett heapSort még:

Feltételezve, hogy egy tömbként ábrázolt max kupacot használsz, és a max elemeket visszahelyezed a kimeneti tömbbe / a tömb hátuljába, ha helyben csinálod , a heapSort legrosszabb esetű bemenete minden olyan bemenet, amely arra kényszerít, hogy “buborékozzon le” vagy újrapéldázzon minden elem eltávolításakor. Ez minden alkalommal megtörténik, amikor duplikát nélküli halmazot próbál rendezni. Ez továbbra is Θ (n log n), ahogy a templatetypedef mondta.

Ez a tulajdonság azt jelenti, hogy a heapSort a legjobb eset, amikor az összes elem egyenlő (Θ (n), mivel nem kell újrapróbálkozni minden eltávolítás után, ami log (n) időt vesz igénybe a a kupac maximális magassága log (n)). Ez egyfajta silány / nem praktikus eset, ezért a heapsort igazi legjobb esete a Θ (n log n).

Megjegyzések

• Az algoritmusok osztályában pont feltették az ön véleményét a szörnyű, nem praktikus esetről. (Óvakodjon a trükkös kérdésektől.) Természetesen én ‘ még mindig egyetértek a véleményével. ( és hibásan kaptam a válaszomat XD)

• Gyors rendezés

  Legrosszabb eset: $ \ mathcal {O} (n ^ 2) $ . Tegyük fel, hogy a pivot elem mindig a jobb szélső elem: Írjon be már rendezett lista $ n $ elemekkel. Tehát minden partíció egy listához vezet $ n-1 $ elemekkel és egy lista a $ 0 $ elemekkel. Még akkor is, ha a pivot elemet véletlenszerűen választja , akkor is lehet, hogy nem szerencsés, és mindig válassza ki a maximális értéket a listában.

  Legyen $ T (n) $ az összehasonlítások száma meg kell rendezni a listát $ n $ elemekkel. Legrosszabb eset: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ rekurzív, $ n $ partícióra)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Legjobb eset: $ \ mathcal {O} (n \ log n) $ . Ha a pivot elemet úgy választják meg, hogy az egyenletesen felosztja a listát:

  \ begin {align} T (n) = & 2 \ T \ balra (\ frac {n} {2} \ jobbra) + n & (\ text {2-szer $ \ frac {n} { 2} $ rekurzív, $ n $ partícióhoz)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {master theorem}) \ end {align}

• Halom rendezés

  A halom rendezés legrosszabb és legbonyolultabb összetétele $ \ mathcal {O} (n \ log n) $ . Ezért a halom rendezéshez $ \ mathcal {O} (n \ log n) $ összehasonlítás szükséges bármely bemeneti tömbhöz. A halom rendezés bonyolultsága:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ kupac}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ kupac}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ szöveg {logaritmus hányados szabály}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {igazítás }

Megjegyzések

• Van ‘ t válaszoltam az összes OP ‘ kérdésre, ezért válaszolok egyre, amelyet hiányoltál; a halomfajta nem ‘ t mindig ugyanannyi összehasonlítást használ egy adott elemhez. A legrosszabb eset a $ a \, n \ log n $, a legjobb esetben pedig a $ b \, n \ log n $, ahol $ a > b $.
• Vegye figyelembe azt is, hogy a háromutas változat lineáris a legjobb eset az egyelemes bevitelhez.