Bij het onderzoeken van de grote O-notatie begrijp ik het concept van O(log n) als een binaire zoekactie en O(n log n) als een snelle sortering.
Kan iemand in lekentaal uitleggen wat het belangrijkste verschil in runtimeis tussen deze twee? en waarom is dat zo?
ze lijken intuïtief op dezelfde manier verwant te zijn
Antwoord 1, autoriteit 100%
Kortom: een factor N.
Een binaire zoekopdracht raakt slechts een klein aantal elementen. Als er een miljard elementen zijn, raakt de binaire zoekopdracht slechts ~30 ervan.
Een quicksort raakt elk afzonderlijk element een klein aantal keren aan. Als er een miljard elementen zijn, raakt de snelle sortering alleaan, ongeveer 30 keer: ongeveer 30 miljard aanrakingen in totaal.
Antwoord 2, autoriteit 79%
Zie hoe Log(n)plat is (niet letterlijk maar figuurlijk, in vergelijking met andere functies), terwijl nLog(n)de 600 heeft overschreden voor een waarde van n = 100. Zo verschillend zijn ze.
Antwoord 3
In eenvoudige termen en visualisatie, ze zijn ongeveer hetzelfde in sorteeralgoritmen, maar snel sorteren omdat O(n log n)een fout heeft in sommige situaties, Snel sorteren is in de meeste situaties >log n, maar in speciale gevallen is n², daarom nvoor log n. Dus snel sorteren voor kleine hoeveelheden sorteren is erg goed, maar voor miljoenen/miljarden is het dat niet, gebruik voor dat soort sorteren beter Samenvoegen samen.