Was ist die Basis des Logarithmus für die Zwecke von Algorithmen?

Alle Logarithmen sind durch eine Konstante verbunden. (Daher die Basisformel ändern ). Da wir Konstanten in der Komplexitätsanalyse generell ignorieren, spielt die Basis keine Rolle.

Normalerweise wird die Basis als 2 betrachtet, wenn der Algorithmus abgeleitet wird. Betrachten Sie eine Art wie merge sort . Sie können einen Baum daraus erstellen, und der Baum hat eine Höhe von log₂ n , da jeder Knoten über eine Höhe verfügt zwei Zweige.

Es spielt keine Rolle, die relative Komplexität ist unabhängig von der verwendeten Basis gleich.

Eine Möglichkeit, um daran zu denken, ist, dass O (log _{2X) = O (log <10> X) = O (log N ) X)}