时间复杂度为 O(log N^3/M) 的算法

Question

我正在尝试编写一个时间复杂度为 O(log N^3/M) 的算法。但是，我不确定 log N/M 部分。如果有人可以确认我的算法是否正确，我将不胜感激。

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

* 如果 for (int i = 1; i < N; i += M)具有 O(N/M) 时间复杂度，O(log N) 需要 i乘以一个常数然后结论是如果我们将常数添加到i可以实现O(log N/M)并同时乘以另一个常数。

O(N/log N) 时间复杂度的算法是什么？

Answer 1

我认为: for (int i = 1; i < N; i += M+i*2)不是 O(log(N/M))因为假设循环将运行 k 次，那么我们有:k*M + 2^k >=N -> 这不会导致 k=O(log(N/M))。

你可以这样写:

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

这显然是 O(log(N/M))。