Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- laufzeit (http://www.informatikerboard.de/board/thread.php?threadid=3355)

Geschrieben von jordy am 12.12.2016 um 19:59:

  laufzeit

Meine Frage:
Bei
(n(n+1))/2 = O(n^2)

und bei

(n(n+1))/2 - 1 = Omega(n^2)

Warum ?


Meine Ideen:
höchster Grad ist 2, also gilt dann wächst asymptotisch gleich schnell wie n^2, aber warum schreibt man das jeweils oben so ?


Geschrieben von eulerscheZahl am 14.12.2016 um 21:37:

 

[latex]\mathcal{O}(n^2)[/latex] heiß, dass es maximal quadratisch ist (könnte auch n oder n*log(n) sein).
[latex]\Omega(n^2)[/latex] heißt mindestens quadratisch (auch n^3 oder 2^n möglich).
Dafür gibt es eigentlich [latex]\Theta(n^2)[/latex]. Das heißt, es ist sowohl als obere als auch als untere Schranke quadratisch.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH