4 
void compute(int n) {
        int h = n;
        while (h > 1) {
            for (int i = 0; i < n; i++) {
                // do some operation
            }
            h = h / 2;
        }
 }

谁能告诉我这个函数的复杂度（Big O）是多少？

这实际上是我和我的一个朋友之间的争论。我的立场：复杂度是 O(n*log(n)) 朋友的立场：log(n)

感谢您的回复。

4

5 回答 5

18

我想说，因为在每次运行中，h 减半并且完成了 n 次操作，它是 O(n * log n)。

于 2009-08-31T07:21:30.713 回答
9

如果这是家庭作业（听起来有点像），那么您应该首先尝试自己。

基本上要获得复杂性，您需要查看函数的结构，即循环、嵌套循环等，并确定它们运行多长时间、它们依赖于哪些输入等。

在这种情况下，您只有一个输入n。局部变量h以与n相同的值开始，因此它在复杂性方面基本相同，但是，您需要跟踪它的使用方式。

这里基本上有两个嵌套循环，一个运行到n，另一个在它周围，这导致h每次运行时减半。所以这个函数在 O( n · log 2 n ) 中。

于 2009-08-31T07:18:57.723 回答
4

一些操作：

O(x)

for 循环：因为 n >= h 并且假设 h 在“某些操作”期间不会被修改：

O(n*x)

外部while循环：

O(log(n)*n*x)
于 2009-08-31T07:27:25.117 回答
0

显然是n*log(h)。

于 2009-11-13T08:06:39.083 回答
0

它似乎是 O(n.sqrt(n))

外循环显然是n，内循环是sqrt(n)。

编辑：内部循环是正确的 log(n)，因为迭代次数是 x，其中 2^x = n。

于 2009-08-31T07:21:13.037 回答