以下循环的(最坏情况)时间分析是什么？

Question

以下是整数变量n的一些代码:

while (n > 0)     
    {         
        n = n/10; // Use integer division     
    }

我试图找到这个循环的最坏情况时间分析.O(n)对我来说是新的,我遇到了困难.这不就是O(n)吗？

Answer 1

实际上该算法的复杂度为 O(log(n))。你正在除以 10（每次循环都去掉一个 0）。

一般来说，如果算法随 n 的大小线性缩放，则其复杂度为 O(n)，但对于这一点，如果将 n 的大小增加 10 倍，则只需再进行一次迭代，而不是 10 倍的迭代次数。环形。

根据要求，这里有几个带有简短入门指南的网站。快速谷歌搜索会发现更多：