Wie bestimme ich, Big-O-Notation

mit Komplexität Was ich brauche, ist eine Erklärung, wie es zu bestimmen, sind hier einige Beispiele und hoffen, dass Sie mir helfen können, ihre Komplexität mit Big-O-Notation zu finden:Wie bestimme ich, Big-O-Notation

For each of the following, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation. 
Consider that we always have n>m. 

Expression Dominant term(s) O(…) 
5+ 0.01n^3 + 25m^3 
500n +100n^1.5 + 50nlogn 
0.3n+ 5n^1.5 +2.5n^1.75 
n^2logn +n(log2m)^2  
mlog3n +nlog2n 
50n+5^3 m + 0.01n^2

Quelle

2016-04-14 Anonymous

Es gibt ein paar Erklärungen von Big O, die Sie vielleicht gelesen haben oder nicht gelesen haben. [Big O, wie berechnen Sie] (http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?rq=1) und [Plain Englisch Erklärung von Big O ] (http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?rq=1). Der Rest der gestellten Frage ist, dass jemand hier etwas tut, was wie eine Hausaufgabe aussieht. – KevinO

Ich stimme zu, diese Frage als off-topic zu schließen, denn als theoretische Frage gehört es auf eine Seite wie Computer Science.SE –

Es ist ziemlich einfach.

Da n zu großen Zahlen ansteigt (gegen unendlich), werden einige Teile des Ausdrucks bedeutungslos, also entfernen Sie sie.

Auch O() Notation ist relativistisch, nicht absolut, was bedeutet, es gibt keine Skala, so dass konstante Faktoren bedeutungslos sind, also entfernen Sie sie.

Beispiel: 100 + 2*n. Bei niedrigen Zahlen 100 ist der Hauptbeitrag zu dem Ergebnis, aber wie n steigt, wird es bedeutungslos. Da es keine Skalierung gibt, ist n und 2n dasselbe, d. H. Eine lineare Kurve, so dass das Ergebnis O(n) ist.

oder die einen anderen Weg wählen Sie die extremsten Kurve im Ausdruck aus dieser graphischen Darstellung: http://bigocheatsheet.com/img/big-o-complexity.png

Lassen Sie uns Ihr zweites Beispiel nehmen: 500n +100n^1.5 + 50nlogn
1. Teil ist O(n).
2. Teil ist O(n^1.5).
3. Teil ist O(nlogn).
Schnellste steigende Kurve ist O(n^1.5), so dass die Antwort ist.

Quelle

2016-04-14 16:49:12 Andreas

Vielen Dank für Ihre ausführliche Antwort, es hat mir wirklich geholfen, einige Schritte herauszufinden, Aber wie Sie sehen können, gibt es andere Beispiele, wo wir verschiedene Typen haben und es gibt eine andere Variable [m]. Wie berechne ich es in diesen anderen Fällen? Danke noch einmal. –

Ich mache nicht all deine Hausaufgaben für dich. Vielleicht sollten Sie diesen Abschnitt lesen: https://en.wikipedia.org/wiki/Big_O_notation#Properties – Andreas

@Moudi die andere Variable ist eine eigene Dimension, nach den gleichen Regeln. Der erste wäre also O (n^3 + m^3) – Carlos

Antwort

Verwandte Themen