在 Theta 表示法中，这段代码的运行时间是怎样的?

Question

我相信func2的运行时是O(n * log(n((。
但有些人告诉我，事实并非如此。

int func2(int* arr, int n){
int i, j;
for (i = 1; i <= n; i *= 2)
reverseArray(arr, i);
}
}
void reverseArray(int* arr, int n){
int left, right, temp;
for (left = 0, right = n-1; left <= right; left++, right--){
temp = arr[left];
arr[left] = arr[right];
arr[left] = temp;
}
}

Answer 1

>func2以线性时间运行，即O(n)

解释：

很容易说反向数组方法的时间复杂度是线性的，即big-Theta(n)

假设func2是用n = 8调用的;

对 reverseArray 的调用将是：-

reverseArray(arr, 1)
reverseArray(arr, 2)
reverseArray(arr, 4)
reverseArray(arr, 8)

所以总运行时间 = 1 + 2 + 4 + 8 = 15，即 2*8 - 1

因此，如果 n 是 2 的幂，则总运行时间 =O(2*n - 1)

如果 n 不是 2 的幂，则总运行时间为 =O(2*K - 1)，其中 K 是小于 n 的 2 的最高幂。我们可以肯定地说，O(2*K - 1) = O(2*n - 1)[因为，O是上限]

O(2*n - 1) = O(n)

对于θ符号，下限是O(2*K - 1)，其中K是小于n的2的最高幂。 因此，时间复杂度 =Theta(2^(floor(log(n)base2)+1))