问排序数组和未排序数组时间复杂度之间的DIfference

EN

让我们看一下您的示例问题:找到两个和等于给定数字的数字。

假设您有一个未排序的数组：[2, 8, 1, 3, 6, 7, 5, 4]，目标是11。

所以你看第一项，2，你知道你必须在数组中找到数字9，如果它存在的话。对于未排序的数组，您必须执行线性搜索，以确定数组中是否存在9。

但是，如果您有一个排序数组，[1, 2, 3, 4, 5, 6, 7, 8]，您有一个优势。当您看到值2时，您知道需要在数组中找到9。但是，因为列表是排序的，所以可以使用二进制搜索。不必查看列表中的每一项，只需查看其中的3项：

二进制搜索将查看第4项，然后是第6项，然后是第8项，最后确定9不在数组中。

简而言之，在一个未排序的数组中搜索需要O(n)时间:您可能需要查看每一项，以确定您要查找的内容是否存在。排序数组使您可以加快搜索速度。不必检查每一项，只需检查最多的log2(n)项。当数字越来越大的时候，这就产生了巨大的差异。例如，如果您的列表包含一百万项，二进制搜索只需要检查其中的20个。顺序搜索必须查看所有的百万。

对于“目标和”问题，排序数组的优点更好:根本不搜索数组。相反，从两端的指针开始。如果和等于目标，则发出该值并将两个指针移入。如果小于目标，则增加较低的指针。否则，减少上指针。这将在O(n)时间内找到所有的解--在取O(n log )作为排序后。

对于注释中给出的情况，[40, 60, 1, 200, 9, 83, 17]流程如下所示：

Sort array:
[1, 9, 17, 40, 60, 83, 200]

Start your pointers at the ends, 1 + 200
The sum is 201, too large, so decrement the right pointer.
Now looking at 1 + 83.  This is too small; increment the left pointer.
Now looking at 9 + 83.  This is too small; increment the left pointer.
Now looking at 17 + 83.  This is the target; print (17, 83) as a solution
    and move *both* pointers.
Now looking at 40 + 60.  This is the target; print (40, 60) as a solution
    and move *both* pointers.
The pointers have now met (and passed), so you're done.

这是一个很好的例子。通常，对数组进行排序比依次检查每个元素要快得多，您可以选择在数组中查找东西。一个简单的二进制搜索是O(log )，有多种方法对特定应用程序进行优化。最坏的情况是，二进制(日志基2)搜索将很好地工作。

但是，对任意列表进行排序需要花费O(n log n)作为开销；您需要根据应用程序的需要计算这一次付款。例如，如果您的数组是按键值(例如名称或ID号)排序的某种数据库，并且必须执行数百万来自用户请求的搜索，那么在进行任何搜索之前最好以某种方式对数据库进行排序。

如果你想要一个彻底的介绍，研究“分类和搜索”。一本很好的参考资料是唐纳德·克努斯( Donald )的书名：“计算机编程艺术”(The Art of Computer Programming)第二卷。