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)
----- Welche Komplexitätsklasse ist O(Wurzel n) * O(Log n)? (http://www.informatikerboard.de/board/thread.php?threadid=3309)

Geschrieben von Tiger87 am 17.11.2016 um 18:54:

  Welche Komplexitätsklasse ist O(Wurzel n) * O(Log n)?

Meine Frage:
Ich habe eine Schleife die mit der Länge Wurzel n. In der Schleife wird ein Algorithmus mit O(Log n) ausgeführt. Liegt die Komplexität in O(n)?

Meine Ideen:
Ich glaube nach den Logarithmusgesetzen müsste man die Wurzel n in den Logarithmus ziehen können. Ich weiß nur nicht ob da jetzt log n^n^1/2 oder log n^1/2 rauskommt.


Geschrieben von eulerscheZahl am 17.11.2016 um 21:37:

 

[latex]\sqrt n \log n = \log(n^{\sqrt n})[/latex], die erste Darstellung würde ich aber bevorzugen.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH