3

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

我的假设是，也许我计算电话的次数是错误的。有人能告诉我哪里错了吗？

4

2 回答 2

5

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

您提供的代码也可以正常工作。关于算法复杂性的混淆已经发生，因为您忽略了 Big-Oh 符号中涉及的隐藏常数以表示复杂性。

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

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

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

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

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

O(n 2 )如果 c 为1使得f(n) = O(1 n 2 )。

O(n 3 )如果 c 为0.1使得f(n) = O(0.1 n 3 )。

于 2013-05-28T12:23:00.967 回答
2

在大 O 表示法中，常数可以忽略不计，因为随着输入 N 的值增加，复杂度不会因常数因素而发生任何变化，变得可以忽略不计。

在这里，在二进制搜索中，发生了 1 个额外的调用。即使你接了十亿个号码，它仍然最多是 1 个额外的电话。因此它变得可以忽略不计，你不需要计算。

于 2013-05-28T12:46:58.763 回答