java - 试图证明二分查找的复杂度是O(log(n))

Question

我正在尝试证明二进制搜索的复杂性。在维基百科中说，最坏的情况是 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);
            }
        }
    }

创意代码: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)。

我的假设是，也许我计算调用次数是错误的。谁能告诉我哪里错了？

Answer 1

二进制搜索大小为 n 的输入的复杂性对于 a > 1 是 O(log_a n) .该算法的本质表明 a=2 ，因为在每次迭代中搜索空间都会减半。

您提供的代码也可以正常工作。关于算法复杂性的混淆是因为您忽略了复杂性的 Big-Oh 符号中涉及的隐藏常量。

声明f(n)= O(g(n))意味着 f(n) ≤ cg(n) .在你的情况下，你忘记承认这个常量 c . c可能大到 100000000000 或小到 0.000000001。这是与 Big-Oh 符号相关的一个问题。对于许多实际目的，由于涉及非常大或非常小的常数，渐近更复杂的算法可能会比渐近更简单的算法执行得更好。

例如，与算法 h = O(n²) 相比，算法 g = O(1000000000 n) 的性能较差, 对于 n < 1000000000 .

所以结论是，因为隐藏常数的参与，你不能简单地通过计算执行的指令数来证明算法的复杂性。你需要有严格的数学方法才能得到证明。

例如一个算法f对输入大小执行 100 指令 n=10可能是，

O(n) 如果 c 是 10 使得 f(n) = O(10 n)。

O(n²) 如果 c 是 1 使得 f(n) = O(1 n ²).

O(n³) 如果 c 是 0.1 使得 f(n) = O(0.1 n ³).