我今天有一个实习面试，我无法弄清楚。
total = 0
product(int array[]) {
if (array.length == 1) {
return array[0]
} else {
product(product right side array * product left side )
}
}
最佳答案
这是 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 的增长，只有更高的阶才重要。
关于arrays - 为什么这是 O(nlogn)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25755281/