algorithm - Theta表示法中此代码的运行时间是什么？

我相信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;
    }
}

最佳答案

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))

关于algorithm - Theta表示法中此代码的运行时间是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52940385/