algorithm - 随机选择复杂度

Question

在分析了算法的复杂性后，我有几个问题:

对于最佳情况的复杂性 - 递归关系是 T(n) = T(n/2) + dn 这意味着复杂性是 Θ(n) .

所以通过大师理论我可以清楚地看到为什么这是真的，但是当我把算法递归调用画成一棵树时我并不完全理解最终的结果。 (似乎我在 log(n) 的高度上有一个分支，在每个级别我都操作一个分区 O(n) - 所以它应该是 nlog(n) 。(只是为了内存——这与 mergeSort algorithem 的最佳情况非常相似，但这里我们忽略分区后不需要的子数组)。

谢谢!

Answer 1

如 Yves Daoust 所写。用实数形象化，即 n=1024

T(n) = T(n/2) + dn
T(1024) = T(512) + 1024
T(512) = T(256) + 512
....
T(2) = T(1) +  2 -> this would be the last operation

因此你得到 1024+512+256+...+1 <= 2048 ，即 2n

你必须考虑一下dn和n一样大, 但在递归关系中 n不是全局变量，它是基于您调用的方法的局部变量。

所以有log(n)打电话但他们不接n -给每个人时间，他们花的时间越来越少。