这个功能的复杂性？

Question

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

任何人都可以告诉我这个函数的复杂性(大O)是多少？

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

谢谢你的回复.

Answer 1

我会说,因为在每次运行中,h减半并且n次操作完成,它是O(n*log n).

Answer 2

如果这是家庭作业(听起来有点像),那么你应该先试试自己.

基本上为了获得complecity,你会看到函数的结构,即循环,嵌套循环等,并确定它们运行的​​时间,它们依赖的输入等.

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

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