如何设计时间复杂度为O（n log n）的搜索算法？
描述一个O（n logn）-时间算法，给定一组由n个整数和另一个整数x组成的S，该算法确定S中是否存在两个元素，其和正好是x。
我计划用二进制搜索来搜索这个。
ALGORITHM(S,x)
S=Insertion-Sort()
for i=1 to S.length
n=x-S[i]
if( Binary-Search(S,n) == true)
return { S[i],n }
Binary-Search(A, v)
low=1
high=A.length
while low ≤ high
mid=(low+high)/2
if v = A[mid]
return mid
if v > A[mid]
low ← mid+1
else
high ← mid−1
return NIL
我如何找到这个算法的时间复杂度？如果T（n）不是（n log n），正确的算法是什么？
共有3个答案
正如其他答案所指出的，您可以首先使用O（n log n）排序，然后在O（log n）时间内搜索每个元素的补码，这样总的来说就等于O（n log n）。
然而，我认为你也可以做以下的事情来得到一个O（n）算法。
注意，如果两个数字之和是x，那么其中一个必须是x
现在为下面数组中的所有元素i构建一个x-i哈希表。这又需要O（n）时间。
现在以每次查找的恒定时间搜索哈希表中的高数组中的每个元素。因此，这也是O（n）。
因此，总体复杂性为O（n）。
算法的整体顺序由单个片段的最高顺序决定。你从一个插入排序开始，它在最坏情况下的性能是O（n^2），所以你已经失败了。
如果要用O（n logn）版本替换排序算法，则必须查看剩下的内容。有一个长度为n的循环，循环体称为二进制搜索。正确编码的二进制搜索是O（logn），因此结果应该是O（nlogn）。添加两个O（n logn）进程仍然会留下O（n logn）。
有另一种更快的方法来完成第二步，但我会留给你去发现。这不会影响整体结果。
-
给定一个整数数组arr，计算元素x，使得x 1也在arr中。如果arr中有重复项，请分别计数。 示例1：输入：arr=[1,2,3]输出：2说明：1和2被计数，因为2和3在arr中。 示例2：输入：arr=[1,1,2]输出：2解释：1计数两次，原因2在arr中。 示例3：输入：arr=[1,1,3,3,5,5,7,7]输出：0说明：没有计算数字，因为arr中没有2、4、6或8。 示例4：输入：a
-
我已经通过谷歌和堆栈溢出搜索，但我没有找到一个关于如何计算时间复杂度的清晰而直接的解释。 说代码像下面这样简单： 说一个像下面这样的循环： 这将只执行一次。 时间实际上被计算为而不是声明。
-
在最近的一次测试中，我们得到了一个函数来计算未排序的ArrayList中出现了多少个double（不是原语double，而是一个项目出现了两次）。 我正确地确定了Big O复杂度为O（N^2），但由于我错误地确定了全部复杂度，因此只获得了部分学分。函数如下： 在他刚刚发布的考试解决方案中，他给出了这样的解释： 输入集合中有N个项，该方法通过一个缩减步骤反复调用自己，该步骤生成一个新索引N次，直到达
-
就像谷歌地图一样，给定一百万个经纬度坐标列表，你将如何打印距离给定位置最近的k个城市？ 我在一次面试中问了这个问题。面试官说这可以在O（n）中通过使用插入排序到k来完成，而不是对整个列表进行排序，即NlogN。我在网上找到了其他答案，大多数人都说NLogN...他[面试官]正确吗？
-
如何计算这些回溯算法的时间复杂度，它们是否具有相同的时间复杂度？如果不一样怎么办？请详细解释并感谢您的帮助。 我实际上有点困惑，对于断字(b)，复杂度是O(2n)，但对于哈密顿循环，复杂度是不同的，对于打印相同字符串的不同排列，以及对于解决n皇后问题，复杂度是不同的。
-
null null T(n)=O(1)+O(nlogn)=O(nlogn) 但我不确定。有人能帮帮我吗。