Mit vielen verschiedenen Auswahl von Sortieralgorithmen, ist es jemals angemessen, einen Algorithmus mit höherer Komplexität in jedem Beispiel zu verwenden?Wann ist es gerechtfertigt, einen O (2^n) -Algorithmus zu verwenden?
Der einzige Grund, an den ich denken kann, ist, wenn es ein sehr kurzes Array gab, oder ein Array, das sehr nahe an der Sortierung war oder nur ein paar verschiedene Zahlen enthielt.
Mit vielen verschiedenen Auswahl von Sortieralgorithmen, ist es jemals angemessen, einen Algorithmus mit höherer Komplexität in jedem Beispiel zu verwenden?
Es kann sein, wenn die Big-O Komplexität der Sorge ein Worst-Case Sie sind sicher, Sie werden nicht getroffen, oder n bekannt ist klein, wie Sie sagen (zB n die Anzahl der weißen Bauern ist links auf einem Schachbrett) und konstante Faktoren sind wichtiger.
O (2^n) ist extrem aber ... Sie müssen auch die Stabilität Ihrer Gründe für die Verwendung berücksichtigen - könnte jemand (einschließlich Sie in der Zukunft) versehentlich den Code ändern, der die Eignung des O (2^n) Algorithmus, und die App manchmal zu sperren, wenn es aufgerufen wird und n ist höher als ursprünglich erwartet oder die Daten sind weniger "freundlich"? Für die meisten Dinge lohnt es sich, die Zeit in den Vordergrund zu stellen, um einen einigermaßen effizienten und hoffentlich wiederverwendbaren Algorithmus zu erstellen, und sich einfach keine Sorgen machen zu müssen, aber manchmal ist das sehr viel komplexer und fehleranfälliger und die CPU- oder Speichervorteile rechtfertigt es nicht. Letztendlich kommt es auf die Auswirkungen - kurz- und langfristig - auf Ihr eigentliches Projekt an.
Oftmals gibt es bei der Erstellung von algorithmischem Code eine einfach zu lösende Methode und eine komplexe, aber effiziente Lösung, und es ist eine gute Idee, den früheren Code schnell zu schreiben, damit Sie ihn verwenden können Testen Sie Letzteres. Die erste kann als "Orakel" -Implementierung bezeichnet werden, weil man darauf vertraut, die Wahrheit zu kennen: die richtige Antwort. Wenn es auch schnell genug ist und Sie Grenzwerte von n oder den Datenszenarien wie besprochen haben, müssen Sie möglicherweise nicht zu der komplexen Implementierung übergehen.
Expanding auf der "dead-easy, offensichtlich Weg, es zu lösen. " Sie müssen möglicherweise einen einmaligen Job machen, der den n^2 Algorithmus sechs Stunden braucht, um zu lösen, nachdem Sie ein paar Minuten damit verbracht haben, es zu schreiben. Der effiziente Algorithmus kann das Problem in ein paar Minuten lösen, aber Sie brauchen ein bis zwei Stunden Entwicklungsaufwand. Sie sind wahrscheinlich mit dem "ineffizienten" Algorithmus besser dran, weil Sie ihn im Hintergrund ausführen können, während Sie an anderen Aufgaben arbeiten. Ich befinde mich regelmäßig in dieser Art von Situation und habe festgestellt, dass die "ineffizienten" Algorithmen oft Zeit sparen. –
Ist 2^n ein Tippfehler für n^2? Ich denke nicht, dass es vernünftige O (2^n) Sortieralgorithmen gibt. –
Ich stimme zu, aber komischerweise habe ich diese genaue Frage in einer Examensarbeit vor kurzem mit 2^n – Dave
Es ist ungewöhnlich. Dennoch könnte O (n^2) vielleicht Sinn ergeben, wenn die n Elemente in einer mehrdimensionalen Ordnung mit komplizierten Anforderungen angeordnet sind, oder man könnte wohl etwas wie das Arrangieren einer Menge von Zahlen in eine Lösung für ein bestimmtes Sudoku "sortieren" sie in eine Lösung, um .... –