algorithm - 将组排序到列表中的决策树

Question

给出时间的下限，以生成 k 组中的 n 个数字的单个排序列表。使得最小的 n/k 在前，依此类推。

所以我已经被这个问题困扰了一段时间，我真的不确定如何去做。我知道如何制作决策树，但我不明白在这个问题的背景下我应该如何做。我不一定理解这个问题，但它似乎足够清晰，可以为人们解决。任何正确方向或澄清的观点将不胜感激。

Answer 1

您的问题很困难，因为它假设n数字已被分成k组，并且组本身是有序的。我将在这里假设每个组中的数字没有排序。如果数字已经在每个组中排序，它会使问题变得微不足道。

解决您的问题的决策树可以用k子树构建，每个组一个，每个子树连接到下一个子树。这样做的原因是组本身已经排序，我们只需要对每个组进行排序。如果我们只需要沿着一条路径遍历这棵树以找到正确的叶节点（和排序列表），就会出现下限运行时间。这意味着下限是树的高度，即：

O(k * lg n/k)

分解这个表达式：

lg n/k是每个k子树的高度

k * lg n/k是完整决策树的高度（有k子树）

请阅读伊利诺伊大学芝加哥分校 CS 401 课程中的出色 PDF，它将完全解释您的原始问题，并向您展示我是如何得出上面给出的 Big Omega 表达式的证据。

Answer 2

我不确定问题中的“下限”是什么。

如果

(...) k 组中的数字。使得最小的 n/k 在前，依此类推。

表示组已经排序（以正确的顺序给出），然后

生成单个排序列表的时间

如果组内的数字已经排序，则为最小值。然后生成排序列表的最短时间是k*(n/k-1) + k*(n/k) + (k-1) = O(n+k)测试每个“k”组是否已经排序，通过按顺序附加每个项目将每个组转换为链表，然后将组连接到单个结果列表或数组中。

另一方面，如果我们想要构建结果所需的最短时间，尽管输入数字在组中的初始（缺少）顺序，那么答案是通用O(k*(n/k)*ln(n/k)) + n = O(n*ln(n/k))算法对每个项目进行排序，然后将所有项目放在结果列表中或数组。kn/kn