java - Big-O在java中的简单解释和使用

Question

<分区>

Answer 1

大 O 用于说明算法随着输入大小的增加而扩展的速度有多快

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

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

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

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

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

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

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

确定 Big 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)。