确定集合中的两个数字是否等于 nlgn 中的 x
Determine if two numbers in a set equals x in nlgn
如果我自己的答案不正确，我不想要解决方案，因为我真的想自己解决这个问题。我想要的是要么是，这是正确的，要么是，这是不正确的，然后是提示或建议，这些提示或建议可能会导致答案而不会破坏它。
问题：
描述一个 theta(nlgn) 时间算法，给定一个由 n 个整数组成的集合 S 和另一个整数 x，确定 S 中是否存在两个元素之和恰好为 x。 （算法简介，2.3-7）
尝试次数：
首先问题没有说明集合是否排序。我假设不是，并使用合并排序对其进行排序，因为在最坏的情况下它是 theta(nlgn)。
然后我说好吧，这仍然是 theta(nlgn) 的唯一方法是如果我递归地将问题分成两部分。我的方法是从数组的索引 i=0 开始，查看 x=i+k 需要什么值 k，然后使用二进制搜索将问题分成两半，直到我找到 k 或找不到。如果我没有找到满足 x=i+k 的 k，那么我将对索引 i=2 到 n-1 继续相同的过程。这将导致 theta(nlgn).
如果删除常量，排序数组和查找 k 的总时间复杂度加起来为 theta(nlgn) + theta(nlgn) = theta(2nlg2n) = theta(nlgn)。
是的，您的解决方案是正确的。不要忘记处理找到的元素 k 具有相同索引 i.
的情况
如果我自己的答案不正确，我不想要解决方案，因为我真的想自己解决这个问题。我想要的是要么是，这是正确的，要么是，这是不正确的，然后是提示或建议，这些提示或建议可能会导致答案而不会破坏它。
问题：
描述一个 theta(nlgn) 时间算法，给定一个由 n 个整数组成的集合 S 和另一个整数 x，确定 S 中是否存在两个元素之和恰好为 x。 （算法简介，2.3-7）
尝试次数：
首先问题没有说明集合是否排序。我假设不是，并使用合并排序对其进行排序，因为在最坏的情况下它是 theta(nlgn)。
然后我说好吧，这仍然是 theta(nlgn) 的唯一方法是如果我递归地将问题分成两部分。我的方法是从数组的索引 i=0 开始，查看 x=i+k 需要什么值 k，然后使用二进制搜索将问题分成两半，直到我找到 k 或找不到。如果我没有找到满足 x=i+k 的 k，那么我将对索引 i=2 到 n-1 继续相同的过程。这将导致 theta(nlgn).
如果删除常量，排序数组和查找 k 的总时间复杂度加起来为 theta(nlgn) + theta(nlgn) = theta(2nlg2n) = theta(nlgn)。
是的，您的解决方案是正确的。不要忘记处理找到的元素 k 具有相同索引 i.