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 logn (http://www.informatikerboard.de/board/thread.php?threadid=3354)
Geschrieben von kalalo am 12.12.2016 um 17:24:
Laufzeit logn
Meine Frage:
Wenn ich in einem Algo mit einer B-Baumstruktur arbeite, muss ich ja im schlimmstem Fall untereGrenze(log2(n)) Operationen durchführen (z.b Heapify auf Heap). Warum wird aber immer O(log(n)) angegeben ?
Meine Ideen:
-
Geschrieben von eulerscheZahl am 14.12.2016 um 21:34:
![[latex]\log_2(n) = \frac{\log(n)}{\log(2)}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\log_2(n) = \frac{\log(n)}{\log(2)})
Die Logarithmen unterscheiden sich nur um einen konstanten Faktor, den kann man in der O-Notation ignorieren.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH