Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

O-Notation
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> O-Notation
 
Autor Nachricht
JoWa
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 13.11.2013
Beiträge: 3

BeitragVerfasst am: 13 Nov 2013 - 16:44:43    Titel: O-Notation

Moin moin,

ich hätte mal eine Frage zur O-Notation.

Nehmen wir an, wir haben eine Tabelle mit m Zeilen und n Spalten.

für jede Zeile wird etwas mit der Komplexität O(n^2) ausgeführt.

Das bedeutet dann doch, dass die Gesamtkomplexität bei O(m * n^2) liegt, was O(k^3) ist? oder bleibt man beim m * n^2?

Gruß
JoWa
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 13.11.2013
Beiträge: 3

BeitragVerfasst am: 16 Nov 2013 - 12:57:49    Titel:

keiner? Sad
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24256

BeitragVerfasst am: 16 Nov 2013 - 23:20:36    Titel: Re: O-Notation

JoWa hat folgendes geschrieben:


Das bedeutet dann doch, dass die Gesamtkomplexität bei O(m * n^2) liegt,


Korrekt.

Zitat:

was O(k^3) ist?


Wenn m und n jeweils in O(k) liegen, ja. Weiß man aber nichts davon (insbesondere, wie sich m und n zueinander verhalten), dann bleibt man eben bei dem einzigen, was man aussagen kann, und so auch bei einem Term in m und n.


Cyrix
JoWa
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 13.11.2013
Beiträge: 3

BeitragVerfasst am: 16 Nov 2013 - 23:37:16    Titel:

vielen dank..

konnte leider nirgends irgendwas darüber finden, ob man mehrere variablen in der klammer haben darf Wink
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24256

BeitragVerfasst am: 16 Nov 2013 - 23:47:14    Titel:

Man muss dann die Definition etwas verallgemeinern, aber doch auf ganz kanonische Weise:

Es ist f(m,n) in O(g(m,n)), wenn es ein c>0 und m_0, n_0 gibt, sodass für alle m>m_0 und n>n_0 nu f(m,n) < c*g(m,n) gilt.


Cyrix
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> O-Notation
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum