arrays - 如何计算 O(Log(N))？

Question

我想确切地知道如何计算这个例子的 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 还是什么？谢谢你的帮助

Answer 1

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

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

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