int func2(int n) {
int i, j;
int sum;
arr = new int[n];
for (i = 0, j = 1; i < n; i++, j *= 2) {
arr[i] = j;
}
sum = 0;
for (i = 0; i < n; i++) {
for (j = 1; j <= arr[i]; j++) {
sum += (i + j);
}
}
delete []arr;
return sum;
}
我的想法:
第一个循环运行 n 次。所以运行时间是 N 的 theta。0(n) +
第二循环
内循环运行。 j 乘以 j= 1+ 2 + 4 + 8。这就是 n(n+1) (2n+1)/6 ==> theta n^3
所以总运行时间 = 0(n)+ 0(n^3)
请对我的答案发表评论,并让我知道我的逻辑是否正确或者我遗漏了什么。我对编程非常陌生。
最佳答案
第一个循环的时间复杂度为 O(n)。
运行第一个循环后,
arr = [1, 2, 4, 8, ... , 2^(n-1)]
所以,第二个循环是
O(1+2+4+ ... +2^(n-1)) = O(2^n - 1) = O(2^n)
总复杂度为
O(n + 2^n) = O(2^n)
关于algorithm - 我需要帮助来验证我的答案。分析函数的运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63894575/