Ist die folgende Aussage wahr oder falsch?Allzweckalgorithmen, die Vorsortierung und ihre Effizienz verwenden
Allzweck-Algorithmen, die Verwendung von Vorsortierung machen kann nie ein Worst-Case-Effizienz haben, die besser als O (n log n) ist
Ich nehme an, es wahr zu sein. Weil das große O dafür ist O (nlogn)
Die Aussage ist wahr, wenn die spätere Phase nicht mehr zeitaufwendig als O(n log n) sein wird. Auch wenn es andere Sortieralgorithmen wie Radix sort, Counting sort, Bucket sort und Pancake sorting gibt, die effizient sind (im Allgemeinen lineare Zeit) als vergleichsorientierte Sortieralgorithmen (O(nlogn)).
Die Implikation der Aussage ist, dass nicht-vergleichende lineare Sortierungen (Zeitkomplexität O (n)) wie Radix-Sortierung die Vorsortierung nicht nutzen kann. Obwohl die Anzahl der Operationen zur Radix-Sortierung nicht durch Vorsortieren beeinflusst wird, wird die Cache-Lokalität sequentieller Schreiboperationen aufgrund vorsortierter Daten die Leistung verbessern.
Ich habe nicht gelernt Radix Sortierung, Zählen Sortierung, Eimer sortieren, Pfannkuchen sortieren. Also nehme ich an, dass die Aussage bis zu diesem Punkt wahr ist. – dyingStudent