Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- O-Notation, mehrere Variablen (http://www.informatikerboard.de/board/thread.php?threadid=2875)

Geschrieben von Hurz am 19.02.2016 um 18:30:

  O-Notation, mehrere Variablen

Hallo,
ich bin gerade dabei mir die O-Notation ein wenig näher zu bringen. Wenn ich zwei verschachtelte Schleifen haben, welche jeweils von 0 bis n laufen, habe ich einen Aufwand von O(n²). Soweit so gut. Wie ist das aber wenn die eine Schleife bis n läuft und die andere bis m? Ist der Aufwand dann immer noch O(n²)?
Vielen Dank für eure Hilfe! smile


Geschrieben von eulerscheZahl am 19.02.2016 um 19:28:

 

Dann hast du [latex]\mathcal{O}(n\cdot m)[/latex].
Wenn du nichts über das Verhältnis von m zu n weißt, musst du das so stehenlassen.
Sollte m maximal um einen konstanten Faktor größer als n sein, kannst du auch [latex]\mathcal{O}(n^2)[/latex] schreiben.


Geschrieben von Hurz am 19.02.2016 um 20:19:

 

Super, vielen Dank!


Forensoftware: Burning Board, entwickelt von WoltLab GmbH