algorithm - 算法复杂性的细节，如何处理日志案例？

Question

我看到了下面的伪代码:

for j=1 to n
    m=n
    while m>0
          //some instructions
          m=m/2

我可以看到外层循环运行了 n 次，但是当它进入 while 部分时，它产生了一系列 m/2。例如，如果 n=10 我会粗略地得到 m 将取 10,5,2,1 的值，所以它大约会迭代 4 次；当 n=100 时，m 的值将是 100,50,25,12,7,3,1 所以大约 7 次迭代。我看到的是 log n(base=2)，所以最终答案是:n*log n。我说得对吗？

我遇到的问题是如何获取 while 循环的详细信息，我可以这样做:

n/2=1
n=2 apply log b=2 to both sides, so I will get:
log (base 2) n=log (base 2) 2
log n=1

我对这最后一部分有疑问，这部分的正确数学推导是什么？

谢谢

Answer 1

您可以将等式重写为重复除以二。

所以我们想在 n/2^x = 1 时找到 x 其中 x 是我们需要执行的除法数 (在这里我将使用 1，因为在实数算术中除以 2 永远不会产生零，并且 1 的近似值对于上限来说已经足够了)

重新排列我们得到 n = 2^x 所以现在我们得到日志 log(n) = x。所以x我们需要达到1，因此内层循环的时间复杂度是log(n)