我试图理解二进制搜索算法的速度。我知道它需要对排序数组进行操作。但是，如果数组未排序而进入并执行排序。排序不是二进制搜索的一部分吗，因此它的性能会变慢？我很困惑，因为我认为，如果数据没有分类，那么使用这种算法的可能性很小。如果我的代码需要对它进行排序，那么为什么不计入搜索算法呢。对不起，如果我不明白，谢谢你的帮助。
j2datikz1#
对。如果数据未分类您只需要搜索一个元素…然后您必须首先对数据进行排序以使用二进制搜索，这总共需要o（n logn+logn）=o（n logn）时间。但一旦对数据进行了排序，就可以对该数据进行任意次数的二进制搜索。你不必每次都重新排序。
ezykj2lf2#
你不能只是指着一个算法说：它有 O(n^2) 复杂性！这是人们通常说的，当然。但那是速记。他们忽略了一些事情；假设听众/读者会做出假设。您需要充分描述精确的算法、应用该算法的条件，以及算法的精确定义 n 以及任何其他变量。然后，你可以回答这个问题。这里的问题是“二进制搜索的性能如何”的定义不清楚。如果你假设它的意思是x，而你的朋友假设它的意思是y，然后你就对答案争论不休，你实际上根本就没有进行建设性的辩论。你只是在摆弄风车；真正的问题是你们两个都不知道问题出在沟通基础上。考虑到这里有一些混乱，我将给你3个不同的或多或少同样合理的更充实的定义，以及每个这样的定义的实际答案。提示，对其中一个来说，“二进制搜索”不是最快的算法！给定[1]一个已经排序的列表和[2]一个值，请编写一个算法来确定该值是否在列表中。最好的答案是：一个二进制排序算法，它的复杂性是 O(log n) .给定[1]一个未排序的列表和[2]一个值，请编写一个算法来确定该值是否在列表中。最好的答案是：遍历列表。它的复杂性将是 O(n) ，二进制排序根本不是这个答案的一部分。给定[1]一个未排序的列表，和[2]一个测试列表，其中每个单独的测试由一个值定义，但它们都使用相同的未排序输入列表，编写一个算法，该算法将为每个测试确定该测试的值是否在列表中，然后给我分摊的复杂性（基本上，整个事情的复杂性，除以我们进行的测试）。那么最好的答案是：首先对清单进行排序，然后是支出 O(n log n) 是时候这样做了，但是我们可以在测试用例计数上进行分摊，然后对每个测试使用二进制搜索，添加一个 O(log n) 每个测试的复杂性。如果我们用术语 n 输入列表的大小和 t 我们的测试数量，让我们： O( (n log n)/t + O(log n) ) 这就是问题的实际答案，尽管看起来很复杂。但是，如果t很大，甚至被认为是无限大，或者我们在这个问题上再增加一个附加条件：[1]中的列表是预先提供给您的，在合理的时间和内存限制内，您可以预处理这些数据，而不需要在测试用例中分摊这些成本那就归结为 O(log n) ，因为t的大值 (n log n) / t 因子接近零。在与你的伙伴交流时，考虑到我们没有在整个科学论文中讨论，有人可能会说：“二进制排序算法的算法复杂性是o（logn）”，即使这忽略了整个故事中的一大块内容。按照第二种情况解释问题（输入未排序，输入包含要搜索的列表和值，没有multi-test子句）。一个说“二进制搜索是o（logn）”的人在第一个或第三个下工作。你们都是对的。注：第三个定义似乎异常复杂。但是，它符合常见的场景。例如，“我们已经整理了一份住在城里的人们的名单和他们的电话号码，我们想把他们打印在一本巨大的书中，目的是让这本书的接收者查找电话号码。我们预计，在一次印刷的生命周期内，该镇的100000名市民平均将进行大约50次查找，总共有500万次查找这个列表。这意味着t=500万，n=200000（假设有20万人住在这里，其中一半人有电话簿）。插入这些号码，对电话簿进行排序，与以任意、未排序的顺序发布电话簿相比，前者以压倒性优势获胜。即使，是的，你开始“放下”整理它的努力，直到有几个人迅速查找了几个电话号码，以弥补你在打印之前整理它的努力，你才能够弥补这一损失。
O(n^2)
n
O(log n)
O(n)
O(n log n)
t
O( (n log n)/t + O(log n) )
(n log n) / t
2条答案
按热度按时间j2datikz1#
对。如果
数据未分类
您只需要搜索一个元素
…然后您必须首先对数据进行排序以使用二进制搜索，这总共需要o（n logn+logn）=o（n logn）时间。
但一旦对数据进行了排序，就可以对该数据进行任意次数的二进制搜索。你不必每次都重新排序。
ezykj2lf2#
你不能只是指着一个算法说：它有
O(n^2)复杂性！这是人们通常说的，当然。但那是速记。他们忽略了一些事情；假设听众/读者会做出假设。
您需要充分描述精确的算法、应用该算法的条件，以及算法的精确定义
n以及任何其他变量。然后，你可以回答这个问题。这里的问题是“二进制搜索的性能如何”的定义不清楚。如果你假设它的意思是x，而你的朋友假设它的意思是y，然后你就对答案争论不休，你实际上根本就没有进行建设性的辩论。你只是在摆弄风车；真正的问题是你们两个都不知道问题出在沟通基础上。
考虑到这里有一些混乱，我将给你3个不同的或多或少同样合理的更充实的定义，以及每个这样的定义的实际答案。提示，对其中一个来说，“二进制搜索”不是最快的算法！
给定[1]一个已经排序的列表和[2]一个值，请编写一个算法来确定该值是否在列表中。
最好的答案是：一个二进制排序算法，它的复杂性是
O(log n).给定[1]一个未排序的列表和[2]一个值，请编写一个算法来确定该值是否在列表中。
最好的答案是：遍历列表。它的复杂性将是
O(n)，二进制排序根本不是这个答案的一部分。给定[1]一个未排序的列表，和[2]一个测试列表，其中每个单独的测试由一个值定义，但它们都使用相同的未排序输入列表，编写一个算法，该算法将为每个测试确定该测试的值是否在列表中，然后给我分摊的复杂性（基本上，整个事情的复杂性，除以我们进行的测试）。
那么最好的答案是：首先对清单进行排序，然后是支出
O(n log n)是时候这样做了，但是我们可以在测试用例计数上进行分摊，然后对每个测试使用二进制搜索，添加一个O(log n)每个测试的复杂性。如果我们用术语n输入列表的大小和t我们的测试数量，让我们：O( (n log n)/t + O(log n) )这就是问题的实际答案，尽管看起来很复杂。但是，如果t很大，甚至被认为是无限大，或者我们在这个问题上再增加一个附加条件：[1]中的列表是预先提供给您的，在合理的时间和内存限制内，您可以预处理这些数据，而不需要在测试用例中分摊这些成本
那就归结为
O(log n)，因为t的大值(n log n) / t因子接近零。在与你的伙伴交流时，考虑到我们没有在整个科学论文中讨论，有人可能会说：“二进制排序算法的算法复杂性是o（logn）”，即使这忽略了整个故事中的一大块内容。
按照第二种情况解释问题（输入未排序，输入包含要搜索的列表和值，没有multi-test子句）。一个说“二进制搜索是o（logn）”的人在第一个或第三个下工作。你们都是对的。
注：第三个定义似乎异常复杂。但是，它符合常见的场景。例如，“我们已经整理了一份住在城里的人们的名单和他们的电话号码，我们想把他们打印在一本巨大的书中，目的是让这本书的接收者查找电话号码。我们预计，在一次印刷的生命周期内，该镇的100000名市民平均将进行大约50次查找，总共有500万次查找这个列表。这意味着t=500万，n=200000（假设有20万人住在这里，其中一半人有电话簿）。插入这些号码，对电话簿进行排序，与以任意、未排序的顺序发布电话簿相比，前者以压倒性优势获胜。即使，是的，你开始“放下”整理它的努力，直到有几个人迅速查找了几个电话号码，以弥补你在打印之前整理它的努力，你才能够弥补这一损失。