为什么归并排序不像斐波那契数列生成的树那样具有 O(2^log(n)) 的时间复杂度？

Question

我理解这两种算法，但是时间复杂度对我来说感觉很奇怪。

如果您查看两种算法生成的两棵树，您会发现它们完全相同，我们不断将树分成两半，直到到达末尾。

那么为什么一种算法的复杂度是 2^N 而另一种算法的复杂度是 nlog(n) ？

Answer 1

O(2^log(n)) 本质上与 O(n) 相同。在你的问题中你提到了 2^n 。您可能想修复这个问题的标题。我不确定斐波那契数列生成的树是什么意思。斐波那契树每个节点有 4 个指针，但我认为这不是您要问的。

简单的递归斐波那契计算是 2^n，因为它重复计算，计算 F(n-1)，进而计算 F(n-2)，然后再次计算 F(n-2)。

对于大小为 2 的幂的数组，在最深层次的递归中，将产生 n 个大小为 1 的子数组实例。然后在下一个最深的级别，合并大小为 1 的运行对的 n/2 个实例，总时间为 O(n)。下一个级别是 n/4 个实例，合并大小为 2 的运行对，总时间也为 O(n)。所以总时间复杂度是O(n log2(n))。

Answer 2

N

中的

2^N

指的是包含树中所有节点的树的深度，表示通过哑双递归函数计算第

N

斐波那契数。因此，该树中的节点数的数量级为

n ~ 2^N

。因此 O(2^N) 实际上意味着 O(n)。花费 O(1) 时间访问每个 O(n) 节点意味着 O(n) 的总复杂度，即 O(2^N)。

归并排序的

n

指的是列表的长度，即底部边缘树的节点数，大约是运行该算法的比较合并的二叉树中节点总数的一半。每个数字平均要上升 log n 层，因此复杂度为 O(n log n)。