algorithm - 在已经指定运行时间时解决算法中的问题，例如 theta(nlogn)

Question

这学期我上过算法课程，我正在尝试解决 CLRS 中的一个问题

2.3-7 描述一个 theta(n lg n) 时间算法，给定一个由 n 个整数组成的集合 S 和另一个整数 x，确定 S 中是否存在两个和正好为 x 的元素。

我不知道如何解决这个问题。我正在尝试使用合并排序算法来解决它，因为它在 nlogn 时间内完成，但我不知道这是否是正确的方法。

谁能告诉我在已经指定运行时间时求解算法的一般方法是什么？

谢谢。

Answer 1

我怀疑此类问题是否有任何通用方法，例如在任何“提议算法”任务中。然而，所需的运行时可以提示要使用的“构建块”（例如存在log通常表示需要树或排序数组）。例如，您可以查看标记 wiki 中的“big-o”，以获取每个所需运行时的算法示例。

针对您的问题的算法想法：

首先，对数组进行排序（O(n lg n)）；然后为y数组的每个元素检查元素x-y是否存在（同样O(n lg n)，因为数组已排序）。