programcode/algorithm 的 运行 时间为 O(n^2 log n)

Question

我必须用上面提到的 运行 时间编写一个 Programm 我知道我将如何使 n log n 成为二进制搜索或 n^2 这将只是 2 个 for 循环。但是我还没有说到要组合它的地步

Answer 1

没有单一的正确方法可以做到这一点。这里有几个选项：

1. 设计一个算法，将 n² 个元素插入到一个平衡的 BST 中。这确实 O(log n) 工作 n² 次。 （这使用了 log n² = 2 log n = O(log n) 的事实。）

2. 使用堆排序或归并排序对 n² 个元素进行排序。更一般地说，运行 任何 O(n log n) 时间算法在大小为 n².

的输入上

3. 写一个递归算法，其运行时间由递归T(n) ≤ 4T(n / 2) + n²给出.这确实 n² 每个级别工作并且具有 O(log n) 级别，并且通过主定理求解到 O(n² log n) .

希望这能让你朝着正确的方向前进。

Answer 2

在其他地方作为问题发布：排序 n 个字符串的最大 运行 时间是多少，每个字符串的长度为 n 个字符？ （提示：字符串比较不是简单的操作）。