Vergleich der zeitlichen Komplexität zweier Algorithmen (Ungleichheit)

Die Frage schlägt vor, dass zwei Algorithmen ausgeben T A ( N ) = 0,0001 N 2 , Und T B ( N ) = 50 N , Mikrosekunden, für eine Problemgröße von N . Die Frage fragt, bei welcher Eingabegröße wird der Algorithmus verwendet A besser werden als B . Wie finde ich das?

Ich habe eine ähnliche Frage mit einer Lösung gefunden, die ich nicht vollständig verstehe. Die Laufzeiten von Algorithmen aus einer ähnlichen Frage sind T A = 0,1 N 2 Protokoll 2 ⁡ N Und T B = 2.5 N 2

Es ist wie folgt gelöst:

2.5 N 2 < 0,1 N 2 Protokoll 2 ⁡ N
2.5 < 0,1 Protokoll 2 ⁡ N
25 < Protokoll 2 ⁡ N
2 25 < N

Daher Algorithmus B ist besser wann N ist größer als 2 25

Ich verstehe das Konzept, Ungleichheit verwenden zu müssen, um dies zu beweisen 0,0001 N 2 < 50 N , es fällt mir jedoch schwer zu verstehen, was in der Lösung für das Beispiel getan wird und wie man es auf die Frage anwendet ...

Ich denke, Ihre Frage ist ein wenig falsch. Das ist wegen N 3 / 2 kann nicht durch eine konstante Größe begrenzt werden, wenn N → ∞ oder anders ausgedrückt, wann N groß genug ist, kann sie durch keine Konstante beschränkt werden.
@Kumar Ich nehme an, es ist möglich, obwohl ich denke, dass es wahrscheinlicher ist, dass ich es anders formuliert habe, als ich es habe, also werde ich es wörtlich wiederholen, und hoffentlich könnte das helfen, die Dinge zu klären. „Die Algorithmen A und B verbringen genau TA(n) = 0,0001n^2 bzw. TB(n) = 50√𝑛 Mikrosekunden für ein Problem der Größe n. Bestimmen Sie die Problemgröße n0, für die der „bessere“ Algorithmus beginnt die anderen unter der Annahme n0 > 0 übertreffen."
Die letzte Aussage Ihres Kommentars sollte eher Ihre eigentliche Frage als ein Kommentar sein. und was auch immer, ich sagte, wird als Antwort gegeben @ DavideFiocco.

Antworten (1)

Angenommen, die beiden Algorithmen lösen dasselbe Problem. In diesem Fall kann man sagen, dass Algorithmus A besser ist als B, wenn T A < T B , weil ersteres in kürzerer Zeit läuft.

Für welche (positiven) Werte von n gilt das T A < T B Ungleichheit halten? Ersetzen der Ausdrücke von T A Und T B du erhältst

0,0001 N 2 < 50 N .

Wie man eine solche Ungleichung mit Stift und Papier lösen kann, erfahren Sie zB hier oder grafisch und algebraisch mit einer Engine für symbolische Mathematik wie Wolfram Alpha. Wenn Sie das tun, werden Sie das sehen T A ist kleiner als T B nur wenn n kleiner als ein Schwellenwert ist. Jenseits dieser Schwelle, Algorithmus B „geht besser als A " weil eine Quadratwurzelfunktion (wie T B ( N ) ) steigt langsamer an als ein quadratischer (wie T A ( N ) ) mit zunehmendem n.

@Varehen Erwägen Sie, dieselbe Frage zu löschen, die auf StackOverflow veröffentlicht wurde stackoverflow.com/questions/58019830/… :)
Vergleich der zeitlichen Komplexität zweier Algorithmen (Ungleichheit)
AntwortenHierDatenschutz-Bestimmungen1y, 0v