2

我想确切地知道如何为这个例子计算 O(Log(N))：我们有一个由 10 个元素组成的排序数组 [1 3 4 8 10 15 18 20 25 30] 当我们进行正常搜索时，我们的复杂度为O(10) 这意味着我们必须检查数组的每个情况，所以 O(10) = 10。但是如果我们进行二分搜索，因为我们有一个排序数组，我们的复杂度为 (O(Log(10))这个符号的结果是什么 O(Log(10))= ??? ? 我有一个误解，我们应该使用 Log base 10 还是 2 或者到底是什么？谢谢你的帮助

4

5 回答 5

14

您误解了算法增长顺序的概念。请阅读一本关于算法的书，让你的概念更强大。无论如何，我会尝试在高层次上解释，

如果您有一个包含 10 个元素的数组，如您所说，并且您进行“正常搜索”（称为线性搜索），则您正在遍历数组中的每个元素，这意味着如果有 'n' 个元素，则有 'n' 个元素必须检查。所以它是 O(n) 而不是 O(10)。如果它是 O(10) [ btw, O(10) = O(1) ] 这意味着它总是需要 10 次或更少的迭代，无论数组中有多少元素，情况并非如此. 如果您的数组有 100 个元素，则需要 100 次迭代，所以我们说顺序是 O(n)，其中 n 是输入大小（这里是数组的大小）。

上面的方法是针对非排序数组的，对于排序数组，我们可以使用更快的方法来搜索，就像你在字典中查找单词一样，这种技术称为二分查找。这里发生的情况是，您查找数组的中间元素，看看您要搜索的数字在哪里，无论是在前半部分还是下半部分。然后，您选择所需的一半并应用相同的分成两半并检查的方法。由于这是递归完成的，它使用对数增长（在二进制搜索的情况下，它是以 2 为底的对数）。请阅读二分搜索和对数增长顺序以获得更好的理解。

于 2013-02-23T18:56:50.040 回答
7

我认为您对为什么二进制搜索是 log(n) 以及为什么它是基数 2 感到困惑。这样想，在二进制搜索的每一步，您都将输入大小减少 2。您需要多少次去做这个 ？您需要以 2 次为底执行此 log n 以将样本量减少到 1。

例如，如果您有 4 个元素，第一步将搜索减少到 2，第二步将搜索减少到 1，然后您停止。因此，您必须将 (4) 记录到基数 2 = 2 次。换句话说，如果 log n base 2 = x，则 2 的 x 次方是 n。

因此，如果您进行二进制搜索，您的基数将是 2。更清楚的是，在您的情况下，Log(10) 基数 2 将是 3.3 左右，即您最多将进行 4 次比较。

于 2013-02-23T20:05:00.107 回答
2

恐怕这不是渐近的工作方式。Big-O 表示法旨在描述算法如何针对可变大小的输入进行缩放。特别是，算法对固定输入（如上所述）所需的操作数将始终保持不变，即 O(1)。类似地，大 O 表示法对常数乘法是不变的。这意味着：

  • O(1) = O(10) = O(Log(10))
  • 对数的基数无关紧要，因为更改基数只会引入一个常数因子
于 2013-02-23T18:51:43.703 回答
1

我有一个误解，我们应该使用 Log base 10 还是 2 或者究竟是什么

不要紧。复杂性没有改变。对数基数 2 与以下内容相同：

Log_2(N) = Log(N) / Log(2)

两者都是 的元素O(Log(N))。

于 2013-02-23T19:19:15.387 回答
0

好吧，O-notation 没有给出复杂度函数的确切值。它给出了增长率。如果你这么说的话

T( n ) = O(lg n )

意味着如果增加n ，搜索n 个元素的数组所需的时间算法不会比 lg n增长得快。

你问的问题应该以不同的方式提出。您可能会问的问题是算法需要多少步迭代（或递归）来搜索n 个元素的数组。

这个问题的答案是算法不需要超过

( int )(lg n )

脚步。

因此，如果您有 10 个元素的数组，那么算法将在不超过 lg 10 = 3 次迭代中找到请求的值（或发现它不存在于数组中）。

于 2019-01-06T10:48:39.153 回答