Wie können wir fast jeden Algorithmus modifizieren, um eine gute Laufzeit zu erreichen?

Dies ist eine Frage von Einführung in Algorithmen von Cormen. Aber das ist kein Hausaufgabenproblem, sondern ein Selbststudium.Wie können wir fast jeden Algorithmus modifizieren, um eine gute Laufzeit zu erreichen?

Ich habe viel nachgedacht und auf Google gesucht. Die Antwort, die ich denken kann, sind: -

Verwenden Sie einen anderen Algorithmus.
Give it Best-Case-Eingänge
einen besseren Computer Verwenden Sie den Algorithmus

Aber ich glaube nicht, diese korrekt sind zu laufen. Das Ändern des Algorithmus ist nicht dasselbe wie das Verbessern der Leistung eines Algorithmus. Auch die Verwendung eines besseren Computers kann die Geschwindigkeit erhöhen, aber der Algorithmus ist nicht besser. Dies ist eine Frage am Anfang des Buches, also denke ich, dass dies etwas Einfaches ist, das ich übersehe.

Also, wie können wir fast jeden Algorithmus ändern, um eine gute Best-Case-Laufzeit zu haben?

Quelle

2013-08-07 Aseem Bansal

Algorithmen am besten sein müssen, Durchschnitts- und Worst-Case-Laufzeiten. Sie können einen Algorithmus nicht zu einer Best-Case-Laufzeit machen, weil er ohnehin einen hat. Vielleicht meinst du _improve_ seine Best-Case-Laufzeit? Bitte schreibe die genaue Frage aus dem Buch. P.S. Die Geschwindigkeit des Computers hat keinen Einfluss auf die zeitliche Reihenfolge eines Algorithmus. – Shahbaz

In diesem Sinne würde ich mir vorstellen, dass die Laufzeit im besten Fall durch einen Eingang mit Nulllänge erreicht werden kann: D – AdamKG

@Shahbaz Das weiß ich. Es hat mich auch verwirrt. Aber der Titel der Frage ist der genaue Wortlaut aus dem Buch CLRS. Ich habe viel Lob für das Buch gehört, daher glaube ich nicht, dass die Aussage falsch sein kann. –

Sie können jeden Algorithmus so modifizieren, dass er eine Best-Case-Zeitkomplexität von O(n) aufweist, indem Sie einen speziellen Fall hinzufügen. Wenn die Eingabe diesem speziellen Fall entspricht, geben Sie eine im Cache gespeicherte hartcodierte Antwort (oder eine andere leicht erhältliche Antwort) zurück.

Zum Beispiel für jede Art, können Sie den besten Fall O(n) machen, indem Sie überprüfen, ob das Array bereits sortiert ist - und wenn ja, geben Sie es so zurück, wie es ist.

Beachten Sie, dass es keine Auswirkungen auf durchschnittliche oder ungünstigste Fälle hat (vorausgesetzt, sie sind nicht besser als O(n)), und Sie verbessern grundsätzlich die Zeitkomplexität des Algorithmus.

Hinweis: Wenn die Größe des Eingangs begrenzt ist, macht die gleiche Optimierung der besten Fall O(1), weil das Lesen der Eingabe in diesem Fall O(1) ist.

Quelle

2013-08-07 12:50:29 amit

Wenn diese Grenze nicht im Algorithmus festgeschrieben ist (von dem ich noch nie gehört habe) "(1)", haben in unserem aktuellen Universum alle Anwendungen beschränkte Eingaben. Die Tatsache, dass Sie einem Algorithmus nicht mehr Zahlen geben können, wird es nicht zu O (1) machen. '(1)' Zum Beispiel 'Summe = 0; für i = 0 bis 100: sum + = array [i]; 'ist ein Algorithmus von O (1), aber natürlich gibt es keine hardcodes Größen im Algorithmus. – Shahbaz

@Shahbaz Obwohl ich dem theoretischen Konzept zustimme, ja - wenn ein Algorithmus eine beschränkte Eingabe hat, dann gibt es eine letzte Menge von Eingaben und somit eine letzte Menge von möglichen Läufen, und die Lösung ist 'O (1)' (begrenzt durch die am längsten von diesen), die Idee war, dass, wenn Ihre Eingabe ein 32bit int ist, das Lesen von 'O (1) 'ist, aber das Iterieren von 1 nach' n 'wird normalerweise als' O (n)' betrachtet, obwohl theoretisch ist es tatsächlich "O (1)". – amit

Ich war gegen Ihren letzten Satz und sagte, der Algorithmus wäre O (1), wenn es begrenzte Eingabe hat. Was ich sagte, ist, dass es im Grunde keinen Algorithmus gibt, der sagt: "Ich akzeptiere nur Eingaben, die von so viel begrenzt sind". Also sind sie theoretisch nicht O (1). Praktisch sind alle Algorithmen in dieser Welt O (1). Kurz gesagt, dieser Satz ist nutzlos. – Shahbaz

Wenn wir eine Anweisung für genau diesen Algorithmus in das Berechnungsmodell des Systems selbst einführen könnten, können wir das Problem einfach in einer Anweisung lösen.

Aber wie Sie vielleicht schon entdeckt haben, ist es ein sehr unrealistischer Ansatz. Somit ist eine generische Methode zum Modifizieren eines Algorithmus, um eine bestmögliche Laufzeit zu erreichen, nahezu unmöglich. Was wir maximal tun können, ist die Anwendung von Optimierungen im Algorithmus für allgemeine Redundanzen, die bei verschiedenen Problemen auftreten.

Oder Sie können naiv gehen, indem Sie die besten Falleingaben nehmen. Aber auch das ändert den Algorithmus nicht wirklich. Tatsächlich ist die Einführung des Algorithmus in das Berechnungssystem selbst, anstatt hochgradig unrealistisch zu sein, auch keine Modifikation des Algorithmus.

Quelle

2015-07-23 07:20:28

Die Möglichkeiten, wie wir den Algorithmus ändern können einen besten Fall zu haben Zeit laufen, sind:

Wenn der Algorithmus an der Stelle ihres Zwecks/Lösung ist, für ex, für eine zunehmende Art Es ist bereits aufsteigende Reihenfolge sortiert und so weiter.

Wenn wir den Algorithmus modifizieren, so dass wir Ausgang und Ausgang für seinen Zweck nur damit mehrere verschachtelte Schleifen zwingt nur ein

Quelle

2017-06-16 14:53:02

Wie können wir fast jeden Algorithmus modifizieren, um eine gute Laufzeit zu erreichen?

Antwort

Verwandte Themen