时间戳

首页 > 解决方案 > 这段代码在 Theta Notation 中的运行时间是多少？

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

问题描述

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

标签： algorithmruntimebig-o

解决方案

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 是 2 小于 n 的最大幂。我们可以有把握地说，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))

推荐阅读