why is this O(nlogn)

Question

我今天参加了一次实习面试，但是我无法解决这个问题。

total = 0

product(int array[]) {

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

- Beto

---

那么你认为应该是什么？ - Juned Ahsan

思考一下为什么算法是对数级别的？提示：在纸上运行此代码并观察发生了什么。然后改变输入的大小，看看你需要在纸上运行代码的时间增加或减少了多少。 （看看问题如何被分解成小问题） - nem035

“产品右侧数组”和“产品左侧”是如何实现的？这是否会对数组进行深度复制？ - templatetypedef

@albert 你是不是想说：product(left side) * product(right side)？我删掉了我的回答，它是错误的。 - JosEduSol

Answer 1

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

想象一下你有多个层级。在第一层中，一个数组中有N个项目，在第二层中，2个数组中有N/2个项目，在第三层中，4个数组中有N/4个项目等等，直到在N个数组中有1个项目。从顶部到底部需要log2(n)个级别。每个值被复制了log2(N)次，这意味着时间复杂度为O(log(N) * N)，因为对数的底数无关紧要。

你可能会说其他操作，比如*和new Array更昂贵，但它们是O(N)，随着N的增长，只有更高的阶数才有影响。

- Peter Lawrey

Answer 2

product（左侧）* product（右侧）将返回一个唯一的数字，因此对product的外部调用将采用O（1）。

这两个内部调用仅仅是在数组中执行二叉树深度优先遍历，这需要O（n）时间。

然而，在每个遍历的层级中，它都在执行对product的外部调用，且有O（logn）个级别，每个级别的成本为O（1），因此该成本乘以O（logn），您就会得到O（nlogn）。

- Mike Dunlavey

---

有N个值，所以无论如何分配工作，只需要(N-1)次乘法。 - Peter Lawrey

@Peter：你说的乘法次数是正确的。 - Mike Dunlavey

Answer 3

原因是当数组长度为1时，时间是恒定的，如果长度为n，则使用具有一半数组的2个递归调用。

稍微正式一点，对数组长度n使用归纳法。在基本情况下，数组的小尺寸为1，显然操作数是一个常数（这与O（nlog n）...和所有内容匹配）。

在一般归纳情况下，数组长度为n，两个递归调用product right side array和product left side都涉及n/2个元素（将数组分为2部分），因此操作数为

n/2 (log n/2) + n/2 (log_2 n/2) = n/2 (log n -1) + n/2 (log n -1) = n log n -2.

在这种情况下，if操作计为1个附加操作，产品*本身计为一个附加操作，总共为nlog n，但添加一个常数是不相关的。

你也可以认为递归调用 product(product right side array * product left side ) 的“深度”是 log n（如果从 256 开始，则递归调用的“深度”将为 8），因为每次数组的大小都是初始大小的一半。由于最终返回了 n 个元素，因此时间复杂度为 O(n log(n))。

- RafaelCaballero

Answer 4

递归树的高度最多为log_2 n，因为这是在到达n = 1（即叶节点）之前可以将n折半的次数 - 将log_2 n视为n中位数的数量。

树的每个级别的宽度最多为n（在底部，每个数组元素仅访问一次；树的上层显然更窄）。

在每个分支处，执行一个常量时间（O(1)）乘法操作（假设对于此参数，数组拆分是恒定时间）。

因此，操作次数的上限为O(1) x n x log_2 n = O(n log n)。

- Rafe