试图证明二分查找的时间复杂度为O(log(n))。

Question

我正在尝试证明二分搜索的复杂度。维基百科上说，最坏情况下的时间复杂度是O(log(n))。这意味着：

如果我的数组有16个元素，log(16)等于4。我应该最多调用4次才能在数组中找到元素。

我的Java代码：

class Main{
      int search(int[] array, int number, int start, int end) {
            System.out.println("Method call");
            int half = (end - start) / 2;

            if (array[start + half] == number) {
                return array[start + half];
            }
            if (array[start + half] < number) {
                return search(array, number, start + half, end);
            } else {
                return search(array, number, start, end - half);
            }
        }

        public static void main(String[] args) {
            int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
            for (int i : array) {
                System.out.println(i);
                new Main().search(array, i, 0, array.length);
            }
        }
    }

Ideaone代码：http://ideone.com/8Sll9n

输出结果如下：

1
Method call
Method call
Method call
Method call
Method call
2
Method call
Method call
Method call
Method call
3
Method call
Method call
Method call
4
Method call
Method call
Method call
Method call
5
Method call
Method call
6
Method call
Method call
Method call
Method call
7
Method call
Method call
Method call
8
Method call
Method call
Method call
Method call
9
Method call
10
Method call
Method call
Method call
Method call
11
Method call
Method call
Method call
12
Method call
Method call
Method call
Method call
13
Method call
Method call
14
Method call
Method call
Method call
Method call
15
Method call
Method call
Method call
16
Method call
Method call
Method call
Method call

除了搜索数字1以外，一切都很好。这里有5个"方法调用"，意味着5大于log（16）。

我的假设是，可能我在计算调用次数时出错了。有人可以告诉我我哪里错了吗？

- chris

---

顺便提一下，log(16) == 1.2 https://www.google.com/search?q=log+16&oq=log+16 - sanbhat

@sanbhat：使用基数为2时，Log（16）为4。 在使用标准计算器或谷歌时转换为基数为2时，执行该求和，然后除以所需的对数，即执行log（16）/ log（2）= 4 - Andrew Martin

为了复杂性的目的，对数的底数是无关紧要的。关于二分查找，以2为底数是直观的，因为我们在每一步中将区间减半。另外，你不能通过检查算法实现的方式来证明其复杂性；证明必须正式完成。 - G. Bach

大O符号（基本上）忽略常数因素。例如，O(g(n)) = O(2.g(n))，或者对于任何常数都是等价的。您可能想阅读一下维基百科页面。 - Bernhard Barker

类似地，O(log(n)) = O(log(n)+1)。 - andrew cooke

http://math.stackexchange.com/questions/191666/how-to-prove-o-log-n-is-true-for-a-binary-search-algorithm - bjskishore123

Answer 1

对于大小为 n 的输入，二分查找的复杂度为 O(log₂ n)，这是由算法本身的特性决定的。您提供的代码也可以正常运行。有关算法复杂度的混淆可能是因为您忽略了大写字母 O 表示法中涉及的隐含常数。表述 f(n)=O(g(n)) 意味着 f(n) ≤ cg(n)。在您的情况下，您忘记了承认这个常数 c。c 可以非常大（例如100000000000）或非常小（例如0.000000001）。这是使用大写字母 O 表示法的一个问题。对于许多实际目的而言，由于涉及非常大或非常小的常数，渐进上更复杂的算法可能会优于渐进上更简单的算法。

例如，当 n < 1000000000 时，算法 g = O(1000000000n) 的性能将比算法 h = O(n²) 差很多。

因此，结论是您不能仅通过计算执行的指令数量来证明算法的复杂度，因为其中涉及到隐藏常数。您需要采用严格的数学方法来进行证明。

例如，对于输入大小为 n = 10 的算法 f 执行 100 条指令时，如果 c 等于 10，那么复杂度为 O(n)，即 f(n) = O(10n)；如果 c 等于 1，那么复杂度为 O(n²)，即 f(n) = O(1n²)；如果 c 等于 0.1，那么复杂度为 O(n³)，即 f(n) = O(0.1n³)。

- Deepu

Answer 2

在大O符号中，可以忽略常数因子，因为随着输入N的增加，复杂度不会因为常数因子而改变，因此可以忽略它。

在二分查找中，会多出一次调用。即使你处理十亿个数字，最多只会多一次调用。因此它可以被忽略，不需要计算在内。

- bjskishore123