O (log N^3/M) 시간 복잡도를 가진 알고리즘

Question

O (log N^3/M) 시간 복잡도로 알고리즘을 작성하려고합니다. 그러나 로그 N/M 부분에 대해서는 잘 모르겠습니다. 내 알고리즘이 올바른지 누군가가 확인해 주시면 고맙겠습니다. for (int i = 1; i < N; i += M)은 O (N/M)의 시간 복잡도를 가지며, O는 (N 로그) 상수를 곱한 것으로 i을 필요

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 

*이면 결론은 O (N/M 로그) 경우에 달성 될 수 있다는 우리는 i에 상수를 추가하고 동시에 다른 상수로 그것을 곱하십시오.

O (N/log N) 시간 복잡도 알고리즘은 무엇이 될까요? 루프가 다음 우리가 가지고있는 케이 번 실행됩니다 말할 수 있기 때문에 for (int i = 1; i < N; i += M+i*2)는 O (로그 (N/M)) 가되지 않습니다 : :

Answer 1

나는 생각 케이 *의 M + 2^K> = N -> 이는 k = 0 (log (N/M))으로 이어지지 않는다.

대신 당신은 쓸 수 :

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

이 분명 O (로그 (N/M))입니다.