大 O,您如何计算 / 近似?

大多数拥有 CS 学位的人肯定会知道Big O 代表什么。它可以帮助我们评估算法的可扩展性。

但是我很好奇, 如何计算或估算算法的复杂性?

答案

我会尽力在这里简单地解释它,但要注意,这个主题需要我的学生花几个月的时间才能最终掌握。您可以在《 Java中的数据结构和算法 》第二章中找到更多信息。


没有机械方法可用于获取 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)

参数Ndata.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 。看一下:索引 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 的数字结束。

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向上时,内部求和结果为负数!那是不可能的,也是错误的。我们需要将总和一分为二,成为iN / 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 主体上的 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²)

大 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 平方。

这勉强可以触及表面,但是当您要分析更复杂的算法时,涉及证明的复杂数学就会发挥作用。希望这至少使您熟悉基础知识。

虽然知道如何弄清楚特定问题的解决时间是很有用的,但了解一些一般情况对于帮助您在算法中做出决策可能会大有帮助。

以下是一些最常见的情况,摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

O(1)- 确定数字是偶数还是奇数;使用恒定大小的查找表或哈希表

O(logn)- 使用二进制搜索在排序数组中查找项目

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

O(n 2 )- 用一个简单的算法将两个 n 位数字相乘;加两个 n×n 矩阵; 气泡排序或插入排序

O(n 3 )- 用简单算法将两个 n×n 矩阵相乘

O(c n )- 使用动态规划找到旅行商问题的(精确)解;使用蛮力确定两个逻辑语句是否等效

O(n!)- 通过蛮力搜索解决旅行商问题

O(n n )- 通常用于代替 O(n!)来得出更简单的渐近复杂度公式

小提醒: big O符号用于表示渐近复杂度(即,当问题的大小增长到无穷大时), 并且它隐藏了一个常数。

这意味着在 O(n)中的算法和 O(n 2 )中的算法之间,最快的方法不一定总是第一个(尽管总存在 n 值,因此对于大小大于 n 的问题,第一个算法是最快的)。

注意,隐藏常量很大程度上取决于实现!

同样,在某些情况下,运行时不是输入大小 n 的确定性函数。以使用快速排序的排序为例:对 n 个元素的数组进行排序所需的时间不是常数,而是取决于数组的起始配置。

时间复杂度不同:

  • 最坏的情况(通常最简单,但并不总是很有意义)
  • 一般情况(通常很难找出...)

  • ...

R. Sedgewick 和 P. Flajolet 撰写的《算法分析入门》就是很好的介绍。

如您所说, premature optimisation is the root of all evil ,(如果可能)在优化代码时应始终使用概要分析 。它甚至可以帮助您确定算法的复杂性。

在这里看到答案,我认为我们可以得出结论,我们大多数人确实确实通过查看算法并使用常识而不是使用例如我们在大学时所考虑的主方法进行计算来近似算法的阶数。话虽如此,我必须补充一点,即使是教授也鼓励我们(以后)实际考虑而不是仅仅进行计算。

我也想补充一下递归函数用法

假设我们有一个类似( scheme code )的函数:

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

递归计算给定数字的阶乘。

第一步是尝试在这种情况下确定函数主体的性能特征, 主体上没有做任何特殊的事情,只是一个乘法(或返回值 1)。

因此, 对于身体性能为:O(1) (恒定)。

接下来,尝试确定此数目以进行递归调用 。在这种情况下,我们有 n-1 个递归调用。

因此, 递归调用性能为:O(n-1) (阶数为 n,因为我们丢弃了无关紧要的部分)。

然后将这两个放在一起,就可以得到整个递归函数的性能:

1 *(n-1)= O(n)


彼得 ,回答您提出的问题;我在这里描述的方法实际上可以很好地解决这个问题。但是请记住,这仍然是一个近似值,而不是一个完整的数学正确答案。这里描述的方法也是我们在大学里教过的方法之一,如果我没记错的话,它用于比本例中使用的阶乘更高级的算法。
当然,这完全取决于您可以对函数主体的运行时间和递归调用的数量进行估计的程度,但是对于其他方法也是如此。

如果您的成本是多项式,则只需保留最高阶项,而无需乘数。例如:

O((N / 2 + 1)*(N / 2))= O(N 2/4 + N / 2)= O(N 2/4)= O(n 2)的

请注意,这不适用于无限系列。尽管在某些常见情况下,以下不等式适用于一般情况,但没有单一的配方:

O(log NNN log NN 2N knn !)

我从信息方面考虑。任何问题都包括学习一定数量的位。

您的基本工具是决策点及其熵的概念。决策点的熵是它将为您提供的平均信息。例如,如果程序包含具有两个分支的决策点,则它的熵是每个分支的概率与该分支的逆概率的对数2之和。这就是您执行该决定所学到的东西。

例如,具有两个可能均相等的分支的if语句的熵为 1/2 * log(2/1)+ 1/2 * log(2/1)= 1/2 * 1 + 1/2 * 1 =1。因此它的熵是 1 位。

假设您正在搜索 N 个项目的表,例如 N = 1024。那是一个 10 位的问题,因为 log(1024)= 10 位。因此,如果您可以使用具有相同可能结果的 IF 语句进行搜索,则应该做出 10 个决策。

那就是您通过二进制搜索得到的结果。

假设您正在执行线性搜索。您查看第一个元素,并询问它是否是您想要的元素。概率是 1/1024,不是 1023/1024。该决策的熵为 1/1024 * log(1024/1)+ 1023/1024 * log(1024/1023)= 1/1024 * 10 + 1023/1024 * 大约 0 = 大约 0.01 位。您学到的很少!第二个决定并不更好。这就是线性搜索如此缓慢的原因。实际上,它是您需要学习的位数的指数。

假设您正在建立索引。假设该表已预先分类为许多 bin,并且您使用键中的所有位中的某些位来直接索引该表项。如果有 1024 个 bin,则对于所有 1024 个可能的结果,熵为 1/1024 * log(1024)+ 1/1024 * log(1024)+ ... 这是 1/1024 * 10 乘以 1024 个结果,或者是该索引操作的 10 位熵。这就是为什么索引搜索速度快的原因。

现在考虑排序。您有 N 个项目,并且有一个列表。对于每个项目,您必须搜索该项目在列表中的位置,然后将其添加到列表中。因此,排序大约需要基础搜索步骤数的 N 倍。

因此,基于具有大致相同可能结果的二元决策进行的排序全都需要 O(N log N)个步骤。如果 O(N)排序算法基于索引搜索,则是可能的。

我发现几乎所有算法性能问题都可以通过这种方式解决。

让我们从头开始。

首先,接受这样的原理,即可以在O(1)时间(即与输入大小无关的时间O(1)内对数据执行某些简单操作。这些在 C 中的原始运算包括

  1. 算术运算(例如 + 或%)。
  2. 逻辑运算(例如 &&)。
  3. 比较操作(例如,<=)。
  4. 结构访问操作(例如,像 A [i] 这样的数组索引,或者跟随 -> 运算符的指针)。
  5. 简单分配,例如将值复制到变量中。
  6. 调用库函数(例如 scanf,printf)。

要证明该原理的正确性,需要对典型计算机的机器指令(原始步骤)进行详细研究。每个描述的操作都可以用少量的机器指令来完成。通常只需要一两个指令。结果,可以在O(1)时间(即,在与输入无关的某个恒定时间量O(1)内执行 C 中的几种语句。这些简单的包括

  1. 在表达式中不包含函数调用的赋值语句。
  2. 阅读声明。
  3. 编写不需要函数调用来评估参数的语句。
  4. 跳转语句中断,继续,转到和返回表达式,其中表达式不包含函数调用。

在 C 语言中,通过将索引变量初始化为某个值,并在每次循环时将该变量递增 1,形成了许多 for 循环。当索引达到某个限制时,for 循环结束。例如,for 循环

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

使用索引变量 i。每次在循环中将 i 递增 1,并且当 i 达到 n − 1 时,迭代将停止。

但是,目前,我们只关注简单的 for 循环形式,即最终值和初始值之间差除以 index 变量递增的数量后,它告诉我们循环了多少次 。除非有某种方法可以通过跳转语句退出循环,否则该计数是准确的。在任何情况下,它都是迭代次数的上限。

例如,for 循环迭代((n − 1) − 0)/1 = n − 1 times ,因为 0 是 i 的初始值,所以 n − 1 是 i 达到的最大值(即,当 i 达到 n-1 时,循环停止,并且 i = n-1)时不发生迭代,并且在循环的每次迭代中将 1 加到 i 上。

在最简单的情况下,每次迭代在循环主体中花费的时间是相同的, 我们可以将主体的 big-oh 上限乘以循环的次数 。严格来说,然后我们必须添加 O(1)时间来初始化循环索引,并添加 O(1)时间以将循环索引与 limit 进行第一次比较 ,因为我们比循环测试多了一次时间。但是,除非可以执行零次循环,否则初始化循环和测试极限一次的时间是可以由求和规则删除的低阶项。


现在考虑以下示例:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

我们知道第(1)行需要O(1)时间。显然,我们绕了 n 次循环,因为我们可以确定,方法是从第(1)行的上限减去下限,然后加 1。由于主体(2)的行花费了 O(1)的时间,我们可以忽略增加 j 的时间以及将 j 与 n 进行比较的时间,两者均为 O(1)。因此,线(1)和(2)的运行时间是n 和 O(1)乘积 ,即O(n)

同样,我们可以限制由(2)到(4)行组成的外部循环的运行时间,即

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

我们已经确定线(3)和(4)的循环需要 O(n)时间。因此,我们可以忽略 O(1)的时间来增加 i 并在每次迭代中测试 i

外循环的初始化 i = 0 和条件 i O(n^2)运行时间。


一个更实际的例子。

在此处输入图片说明

如果您想凭经验估计代码的顺序,而不是通过分析代码,则可以坚持使用一系列递增的 n 值和时间来增加代码时间。在对数刻度上绘制您的时间。如果代码是 O(x ^ n),则值应落在斜率 n 的直线上。

与仅研究代码相比,这具有多个优点。一方面,您可以看到您是否处于运行时间接近其渐近顺序的范围内。同样,您可能会发现某些您认为顺序为 O(x)的代码实际上是顺序为 O(x ^ 2),例如,由于在库调用中花费了时间。

基本上 90%的时间都收获的东西只是分析循环。您有单,双,三嵌套循环吗?您有 O(n),O(n ^ 2),O(n ^ 3)运行时间。

极少数情况下(除非您正在编写带有扩展基础库的平台(例如. NET BCL 或 C ++ 的 STL),否则您会遇到比仅查看循环(语句,而 goto,等等...)