Ci sono alcune domande da porsi quando si tratta di grandi quantità di dati (lascio "grandi" intenzionalmente vaghe).
-
Tutti i dati possono essere caricati contemporaneamente nella memoria?
-
La quantità di dati è nota in anticipo? Oppure potrebbe entrare di più mentre l'algoritmo è in fase di elaborazione?
-
È possibile ordinare i dati prima di analizzarli?
La maggior parte degli esercizi a livello universitario tendono a gestire piccole quantità di dati, quindi queste domande non contano. Tuttavia, considera Google: hanno enormi quantità di dati e il caricamento dell'intero indice di ricerca in memoria e l'ordinamento non è affatto vicino possibile.
Anche quando la quantità di dati potrebbe entrare in memoria, a volte le soluzioni migliori sono quelle che funzionano nel caso più ampio. Ad esempio, potrebbe non essere necessario ordinare questo array per trovare gli elementi più grandi. Da una prospettiva teorica, la notazione Big-O è grande: tuttavia, nel mondo reale, a volte il fatto che O (n + n log n) si semplifichi a O (n log n) non è una grande rassicurazione. Potrebbe tradursi in minuti o ore di tempo di esecuzione extra.
Analisi Big-O:
-
Mentre il link che hai postato afferma che è O (n), così come Wikipedia , non sono d'accordo . Big-O riguarda la complessità di worst-case , che in realtà è O (n 2 ). Mentre il caso medio è n (non c'è una lettera per quello), il caso peggiore è un enorme killer del tempo.
-
L'array viene ripetuto una volta, che è O (n). La modifica dell'heap binario è O (log 2 k), ma viene eseguita (caso peggiore) n volte. Questo rende il tutto O (n + n log 2 k) = O (n log 2 k). Tieni inoltre presente che k è piccolo rispetto a n e che log 2 k è ancora più piccolo.
-
L'ordinamento della selezione parziale in questa istanza è O (kn).
La prima opzione potrebbe in teoria comportarsi bene la maggior parte del tempo, con alcuni set di dati che funzionano male.
La seconda opzione funzionerà molto bene tutto il tempo. Nel peggiore dei casi, è molto meglio del primo algoritmo. Tuttavia, il primo algoritmo potrebbe sovraperformare questo tempo.
La terza opzione è praticamente costante per un dato n : il contenuto dell'array non ha importanza, solo la sua dimensione.
Vorrei puntare a me stesso verso l'heap binario, ma potrebbe valere la pena analizzare se i dati darebbero l'algoritmo Quickselect un momento difficile e forse implementarli entrambi e misurare la loro velocità reale.