Possiamo dire che, quando tutti gli elementi sono identici in una matrice A di dimensione n allora il tempo di mucchio sorta di esecuzione è O esecuzione (n)momento mucchio sorta, quando tutti gli elementi sono identici
-> Se questo è il caso, è O (n) il miglior tempo di esecuzione dell'heapsort
Quando tutti gli elementi sono uguali, l'heap richiede O (n) passi. Perché quando l'elemento viene aggiunto all'heap dopo aver confrontato O (1), vediamo che si trova nella posizione corretta.
La rimozione della radice è anche O (1), quando scambiamo la coda e la radice, la proprietà heap è ancora soddisfatta.
Tutti gli elementi vengono aggiunti all'heap in O (n) e rimossi in O (n). Quindi, sì in questo heapsort del caso è O (n). Non riesco a pensare a un caso migliore, quindi il caso migliore dovrebbe essere O (n).
'Il caso migliore di Heapsorts è O (n)' significa in inglese qualcosa come: esistono matrici di dimensione n tali che heapsort ha bisogno al massimo di k * n per ordinarlo. Questo è bello in teoria, ma in pratica non dice molto su quanto sia buono o veloce l'heap.
Grazie .. Ishtar – rakesh
Questo NON è corretto! vedi http://stackoverflow.com/questions/4589988/lower-bound-on-heapsort – Cheng
@Cheng, Questa domanda riguarda il caso ** migliore **, la domanda che hai collegato riguarda il caso ** peggiore **. Come ho sottolineato, il caso migliore non è davvero pertinente. Se hai suggerimenti su come migliorare la mia risposta, fammi sapere. – Ishtar