1

我真的不知道“Big-O”是什么以及如何在实践中使用它，所以我希望有人能给我一个简单的解释，也许还有一个java中的小编程示例。

我有以下问题：

  • 这些术语是什么意思（尽可能简单）以及它如何在 java 中使用：BigO(1)、BigO(n)、BigO(n2) 和 BigO(log(n))？

  • 如何从现有的 java 代码中计算 Big-O？

  • 如何使用 Big-O 排序
  • 如何使用 Big-O 递归

希望有人能够提供帮助。

谢谢你的好处

4

3 回答 3

5

Big O 用于了解算法随着输入大小的增加而扩展的速度

O(1) 表示随着输入大小的增加，运行时间不会改变

O(n) 意味着随着输入大小加倍，运行时间将加倍，或多或少

O(n^2) 意味着当输入大小加倍时，运行时间将增加四倍，或多或少

O(f(n)) 意味着随着输入大小翻倍，运行时间将增加到 f(2n) 左右

关于 Big-O、排序和递归。

Big-O 排序并不是真正的算法。但是，您可以使用 Big O 来告诉您排序算法的速度。

为了计算递归函数的 Big-O，我建议使用Master Theorem。

确定大 O 的指南：

通常，您需要确定输入大小是多少（例如数组长度或链表中的节点数等）

然后问自己，如果你的输入大小翻倍会发生什么？还是三倍？如果您有一个遍历每个元素的 for 循环： 

//say array a has n elements
for (int i = 0; i < n; i++) {
    // do stuff 
    a[i] = 3;
}

然后将 n 加倍会使循环运行时间增加一倍，所以它是 O(n)。将 n 增加三倍将使所需时间增加三倍，因此代码随输入大小线性缩放。

如果您有一个二维数组并嵌套了 for 循环：

// we say that each dimension of the array is upper bounded by n,
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // do stuff
        a[i][j] = 7;
    }
}

当 n 翻倍时，代码将花费 2^2 = 4 倍的时间。如果输入大小增加三倍，代码将花费 3^2 = 9 倍的时间。所以大 O 是 O(n^2)。

于 2013-06-14T22:32:43.777 回答
2

Big-O 表示法是一种用于在输入非常大时显示计算机算法性能的表示法。

三个快速编程示例，用 Java 编写：

O(1):

for (int i=0; i<3; i++) {
   System.out.println(i);
}

O( n ):

int n = 1000000; /* Some arbitrary large number */    
for (int i=0; i<n; i++) {
   System.out.println(i);
}

O( n 2 ):

int n = 1000000; /* Some arbitrary large number */    
for (int i=0; i<n; i++) {
   for (int j=0; j<n; j++) {
      System.out.println(i * j);
   }
}

阅读更多：http ://en.wikipedia.org/wiki/Big_O_notation

于 2013-06-14T22:38:36.030 回答
1

大 O（它是字母 O——它是大的——而不是字母 o 是小）给出了当输入大小 (n) 变化时算法如何缩放的概念。数字是

例如，如果 n 从 100 到 200 个项目翻倍，

  • O(1) 算法将花费大约相同的时间。
  • O(n) 算法将花费双倍的时间。
  • O(n^2) 算法将花费四倍的时间 (2^2)
  • O(n^3) 算法将花费八倍的时间 (2^3)

等等。

注意log(n)可以理解为“n中的位数”。这意味着如果您从 n 有两位数（如 99）到 n 有双位数（如 9999 的四位数），则运行时间只会加倍。这通常发生在您将数据分成两堆并分别求解并合并解决方案时，例如在排序中。

通常，输入数据上的每个循环都乘以 n。所以一个循环是 O(n)，但如果你需要将每个元素与每个其他元素进行比较，你会得到 O(n^2)，依此类推。请注意，时间是相对的，因此对于较小的 n 值，快速 O(n^2) 算法可能优于慢速 O(n) 算法。

还要注意 O 是最坏的情况。因此，通常快速运行的快速排序仍然是 O(^2)，因为存在可悲的输入数据，导致它将每个元素相互比较。

这很有趣，因为大多数算法对于小数据集来说都很快，但是您需要知道它们如何处理可能大数千或数百万倍的输入数据，如果您有 O(n^2) 或 O(n^3)，这很重要) 或更糟。这些数字是相对的，因此如果给定的算法是慢速或快速，它不会说出任何 bps 的信息，而当你将输入大小加倍时，最坏的情况会是什么样子。

于 2013-06-14T23:03:51.260 回答