arrays - 为什么这是 O(nlogn)

Question

我今天有一个实习面试，我无法弄清楚。

total = 0

product(int array[]) {

    if (array.length == 1) {
        return array[0]
    } else {
        product(product right side array  * product left side )
    }
}

Answer 1

这是 O(N log N) 因为每个值被复制的次数是 O(log N)。

想象一下，您有多个级别。在第一级有 N 个项目在一个数组中，在第二级有 N/2 个项目在 2 个数组中，在第三级有 N/4 个项目在 4 个数组中等等，直到你在 N 个数组中有 1 个项目。这需要 log2(n) 级别从上到下。每个值都被复制了 log2(N) 次，这意味着时间复杂度是 O(log(N) * N)，因为日志的基数并不重要。

你可能会说其他操作如 *和 new Array更昂贵，但是这些都是 O(N) 并且随着 N 的增长，只有更高的阶才重要。