algorithm - 这段代码在 Theta Notation 中的运行时间是多少？

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)

解释:

很容易说 reverseArray 方法的时间复杂度是线性的，即 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)

对于 theta 表示法，下限是 O(2*K - 1)，其中 K 是 2 小于 n 的最高次方。因此，时间复杂度 = Theta(2^(floor(log(n)base2)+1))