www.mikrocontroller.net

Forum: PC-Programmierung O Notation - Ist O(n) + O(log n) = O(n)?


Autor: LL0rd (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Leute,

eben nur ganz kurz eine Frage: Ist O(n) + O(log n) = O(n) ?

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja.

Autor: LL0rd (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dankeschön!

Autor: Rolf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D.h. O(log(n)=0 oder was?

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein, O(f(n)) ist eine Menge. Und + bedeutet bei Mengen üblicherweise 
"Vereinigung".

O(n) + O(log n) ist also die Vereinigung der Mengen O(n) und O(log n). 
Und da O(log n) nur eine Teilmenge von O(n) ist, ist die Vereinigung 
genau O(n).

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und weils grad so schön ist, nehmen wir das Mooresche Gesetz als gegeben 
an, und beweisen O(2^n)=O(n). ;)

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Ernst Bachmann:

Da du ein Freund des großen O zu sein scheinst: Bist du vielleicht ein
Nachfahre vom Paul, der diese Notation lt. Wikipedia als erster
verwendet hat?

  http://de.wikipedia.org/wiki/Paul_Bachmann_(Mathematiker%29

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.