fnB 中大 O 表示法的执行时间是多少?

Question

我有 2 个函数，我需要在 Big O 中找到这两个函数的执行时间，但我对 fnB 感到困惑

int fnA(int n){
int sum = 0;
for(int i=0; i<n; i++){
for(int j=n; i<j; j=j-2){
sum += i*j;
}
return sum;
}

我得到了 O(n^2( for fnA

int fnB(int n) {
int sum =0;
for(int size = 1; size<n; size=2*size){
sum+=fnA(size);
}
return sum;
}

由于在 fnB 中的 for 循环中，大小呈指数级增长。我倾向于 fnB 有一个 O(n^3(。我是否正确，如果不是，请纠正我，谢谢

Answer 1

fnA的运行时间为 O(n²(。

但是，fnB的运行时间为 O(n 2 logn(，因为它有 log 2 n 次迭代，并且每次迭代需要 O(n 2( 时间(实际上需要 O(大小 2(，但从size<n>²( 绑定(。

更详细的解释：

fnA(n)在外循环中有n次迭代，在内循环中最多有n/2次迭代，这给出了 O(n²( 上限。由于每次迭代fnB(n)调用fnA(size)，它需要 O(大小²( == O(n²( (自size

现在，fnB(n)循环将以下值分配给size：2⁰， 2¹， 2²， ...， 2 k，其中 2^k<= n。因此，迭代次数为 k <= log 2 n，fnB的上限为 O(n 2 log²n(。

Answer 2

Big-O表示法可用于表示算法的时间复杂度或空间复杂度。

在你的程序中，函数 fnA 可以被认为是具有 O(n^2( 的时间复杂度，因为它有两个嵌套的for循环。 但是，由于条件i<j的计算结果始终为 false，内部for循环将永远不会执行。因此，fnA函数更现实的时间复杂度是 O(n(。

fnB函数在单个for循环中调用fnA。因此，它的时间复杂度为 O(n^2(。