care este timpul de funcționare al extragerii dintr-un Max Heap?

Am această întrebare tematică

"James susține că reușește să implementeze extragerea dintr-o grămadă maximă (ExtractMax), care ia O ((log n) ^ 0.5)

     

explică de ce James greșește

Știu că extragerea din grămada maximă durează O (log n), dar cum pot dovedi că James este greșit?

0

2 răspunsuri

După cum se poate vedea aici , construirea unui heap se poate face în O (n). Acum, dacă extragerea maximului ar putea fi făcută în O ((log n) ^ 0.5), atunci ar fi posibil să sortați întregul set în n * O ((log n) ^ 0.5) extragând în mod repetat cel mai mare element. Aceasta, cu toate acestea, este imposibilă, deoarece limita inferioară pentru sortare este n * logn.

Prin urmare, lui James nu există.

0
adăugat
Corect! Cu o modificare minoră: Limita inferioară pentru comparație-sortare este n * logn. Puteți să sortați radix în O (n).
adăugat autor usr, sursa
Radix sortează în O (n)? Numai dacă presupuiți un număr constant de valori diferite pe care doriți să le sortați (de exemplu 2 ^ 32). În caz contrar, este n * [lungimea reprezentării], unde [lungimea reprezentării] va fi log (n).
adăugat autor Dino, sursa
O abordare foarte inteligentă, dar cred că este un pic cam suprasolicitat
adăugat autor acattle, sursa

@ Soluția lui Duh de a converti problema dvs. de extracție într-o problemă de sortare este de fapt foarte creativă. Nu ar trebui să fie prea greu să găsiți dovezi că sortarea este O (n * log n) și este foarte comună în studiul algoritmilor pentru a converti o problemă într-una diferită (de exemplu, toate problemele NP-Complete sunt conversii ale unul pe celălalt. Așa dovediți că sunt NP-Complete). Acestea fiind spuse, cred că există o soluție mult mai simplă.

Ați spus-o direct în întrebarea dvs.: extragerea dintr-un heap binar este O (log n). Gândiți-vă la de ce este O (log n). Care este structura unei grămezi binare? Ce acțiuni sunt necesare pentru a extrage dintr-un heap binar? De ce este cel mai rău caz log n operații? Aceste limite sunt influențate deloc de implementare?

Acum, amintiți-vă că există două părți la revendicarea lui James:

  1. Poate extrage în O ((log n) ^ 0.5)
  2. Folosește un heap binar.

Având în vedere ceea ce știi despre haldele binare, ambele aceste afirmații pot fi adevărate? De ce sau de ce nu? Există o contradicție? Dacă da, de ce există o contradicție? În sfârșit, gândește-te la ce înseamnă asta pentru James.

0
adăugat