协慌网

大多数拥有 CS 学位的人肯定会知道Big O 代表什么。它可以帮助我们衡量算法的实际效率（如何），如果你知道你试图解决的问题属于哪个类别，你可以弄清楚是否仍然可以挤出那么少的额外性能。 ¹

但我很好奇， 你如何计算或近似算法的复杂性？

¹ _{但正如他们所说，不要过度， 过早优化是所有邪恶的根源，没有正当理由的优化也应该得到这个名称。}

我将尽力以简单的术语在这里解释，但请注意，这个主题需要我的学生几个月才能最终掌握。您可以在 Java书籍的 “ 数据结构和算法”的第 2 章中找到更多信息。

没有可用于获取 BigOh 的机械程序 。

作为 “食谱”，要从一段代码中获取BigOh ，首先需要意识到您正在创建一个数学公式来计算在给定一定大小的输入的情况下执行多少计算步骤。

目的很简单：从理论的角度比较算法，而无需执行代码。步数越少，算法越快。

例如，假设你有这段代码：

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

此函数返回数组所有元素的总和，我们想要创建一个公式来计算该函数的计算复杂度 ：

Number_Of_Steps = f(N)

所以我们有f(N) ，一个计算计算步数的函数。函数的输入是要处理的结构的大小。这意味着调用此函数，例如：

Number_Of_Steps = f(data.length)

参数N取data.length值。现在我们需要函数f()的实际定义。这是从源代码完成的，其中每个有趣的行编号从 1 到 4。

有很多方法可以计算 BigOh。从这一点开始，我们将假设每个不依赖于输入数据大小的句子采用恒定的C数计算步骤。

我们将添加函数的各个步骤数，并且局部变量声明和 return 语句都不依赖于data数组的大小。

这意味着第 1 行和第 4 行各占用 C 个步数，函数有点像这样：

f(N) = C + ??? + C

下一部分是定义for语句的值。请记住，我们正在计算计算步骤的数量，这意味着for语句的主体被执行了N次。这与添加C ， N次相同：

f(N) = C + (C + C + ... + C) + C = C + N * C + C

没有机械规则来计算for的主体被执行的次数，你需要通过查看代码的作用来计算它。为了简化计算，我们忽略了for语句的变量初始化，条件和增量部分。

为了得到实际的 BigOh，我们需要对函数进行渐近分析 。这大致是这样做的：

1. 带走所有常数C
2. 从f()得到standard form的多项式 。
3. 划分多项式的项，并按增长率对它们进行排序。
4. 当N接近infinity大时，保持那个变大的那个。

我们的f()有两个术语：

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

取走所有C常数和冗余部分：

f(N) = 1 + N ^ 1

由于最后一个术语是当f()接近无穷大时会变大（考虑极限 ），这是 BigOh 参数，而sum()函数的 BigOh 为：

O(N)

有一些技巧可以解决一些棘手的问题：尽可能使用求和 。

例如，使用汇总可以轻松解决此代码：

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

你需要问的第一件事是执行foo()的顺序。虽然通常是O(1) ，但你需要向你的教授询问它。 O(1)表示（几乎，大部分）常数C ，与N大小无关。

关于第一句的for语句很棘手。当索引以2 * N结束时，增量由 2 完成。这意味着，第一for被执行仅N步骤，我们需要除以 2 计数。

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

语句编号二是更加棘手，因为它取决于价值i 。看看：索引我取值：0,2,4,6,8，...，2 * N，第二个for执行：第一个 N 倍，N - 2 秒，N - 4，第三... 到 N / 2 阶段，在其上第二for永远不会被执行。

在公式上，这意味着：

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

我们再次计算步数 。根据定义，每个求和应始终从 1 开始，并以大于或等于 1 的数字结束。

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

（我们假设foo()是O(1)并且采取C步骤。）

我们这里有一个问题：当i向上取值N / 2 + 1时，内部求和以负数结束！这是不可能的，也是错的。我们需要将总和分成两部分，这是i拿N / 2 + 1的关键点。

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

由于关键时刻i > N / 2 ，内部for将不会被执行，并且我们假设其身体上的 C 执行复杂度不变。

现在可以使用一些标识规则简化摘要：

1. 求和（w 从 1 到 N）（C）= N * C.
2. 求和（w 从 1 到 N）（A（+/-）B）= 求和（w 从 1 到 N）（A）（+/-）求和（w 从 1 到 N）（B）
3. 求和（w 从 1 到 N）（w * C）= C * 求和（w 从 1 到 N）（w）（C 是常数，与w无关）
4. 求和（w 从 1 到 N）（w）=（N *（N + 1））/ 2

应用一些代数：

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

而 BigOh 是：

O(N²)

Big O 给出了算法时间复杂度的上限。它通常与处理数据集（列表）结合使用，但可以在别处使用。

它是如何在 C 代码中使用的几个例子。

假设我们有一个 n 个元素的数组

int array[n];

如果我们想要访问数组的第一个元素，那么这将是 O（1），因为数组的大小并不重要，它总是需要相同的常量时间来获取第一个项目。

x = array[0];

如果我们想在列表中找到一个数字：

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

这将是 O（n），因为至多我们必须查看整个列表才能找到我们的号码。 Big-O 仍然是 O（n），即使我们可能会发现我们的数字是第一次尝试并且通过循环一次，因为 Big-O 描述了算法的上限（omega 用于下限，theta 用于紧束缚） 。

当我们到达嵌套循环时：

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

这是 O（n ^ 2），因为对于外环的每次通过（O（n）），我们必须再次遍历整个列表，因此 n 的乘法使我们得到 n 平方。

这几乎没有触及表面，但是当您分析更复杂的算法时，涉及校样的复杂数学就会发挥作用。希望这至少让你熟悉基础知识。

虽然知道如何找出特定问题的大 O 时间是有用的，但了解一些一般情况可以帮助您在算法中做出决定。

以下是一些最常见的案例，取自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions ：

O（1） - 确定数字是偶数还是奇数; 使用常量查找表或哈希表

O（logn） - 使用二进制搜索查找已排序数组中的项

O（n） - 在未排序的列表中查找项目; 添加两个 n 位数字

O（n ² ） - 通过一个简单的算法乘以两个 n 位数字; 添加两个 n×n 矩阵; 冒泡排序或插入排序

O（n ³ ） - 通过简单算法乘以两个 n×n 矩阵

O（c ⁿ ） - 使用动态规划找出旅行商问题的（精确）解决方案; 使用强力确定两个逻辑语句是否相等

O（n！） - 通过暴力搜索解决旅行商问题

O（n ⁿ ） - 经常使用而不是 O（n！）来推导渐近复杂度的简单公式