Algorithmus mit O (log N^3/M) Zeit Komplexität

Question

Ich versuche, einen Algorithmus mit O (log N^3/M) Zeit Komplexität zu schreiben. Ich bin mir jedoch nicht sicher über log N/M Teil. Ich wäre dankbar, wenn jemand bestätigen könnte, ob mein Algorithmus korrekt ist.

for (int i = 1; i < N; i = i*2) // log N 
    for (int i = 1; i < N; i = i*2) // log N 
    *for (int i = 1; i < N; i += M+i*2) // log N/M 

* If for (int i = 1; i < N; i += M) O (N/M) Zeitkomplexität aufweist und O (log N) erfordert i mit einer Konstanten multipliziert werden, dann ist die Schlussfolgerung, dass O (log N/M) erreicht werden kann, wenn wir fügen die Konstante zu i hinzu und multiplizieren sie gleichzeitig mit einer anderen Konstante.

Was wäre ein Algorithmus für O (N/log N) Zeitkomplexität?

Answer 1

Ich denke, dass: for (int i = 1; i < N; i += M+i*2) nicht O (log (N/M)) da können sagen, dass die Schleife für k mal ausgeführt wird, dann haben wir: k * M + 2^k> = N -> was nicht zu k = O führt (log (N/M)).

Stattdessen könnten Sie schreiben:

for (int i = 1; i < N/M; i =i*2) 

dies offensichtlich O (log (N/M)).