试图证明二进制搜索的复杂性是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);
            }
        }
    }

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).

我的假设是,我可能错了计算电话.有人能告诉我哪里错了吗？

Answer 1

二进制搜索的用于大小的输入的复杂度n是O(登录_一个 n)的对a > 1.算法的本质表明a=2,因为在每次迭代时搜索空间都减半了.

您提供的代码也正常工作.关于算法复杂性的混淆已经发生,因为您忽略了Big-Oh表示复杂性中隐藏的常量.

声明f(n)= O(g(n))意味着f(n) ? cg(n).在你的情况下,你忘了承认这个常数c.c非常可能大到1000亿或小到0.000000001.这是与Big-Oh表示法相关的一个问题.对于许多实际目的,由于涉及非常大或小的常数,渐近更复杂的算法可能会执行渐近更简单的算法.

例如,该算法G = O(十亿n)的当与算法相比会给性能差H =为O(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 ³).