algorithm - 大写theta - 算法复杂度大o




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

大多数拥有CS学位的人肯定会知道Big O代表什么。 它可以帮助我们评估算法的效率(效率),如果您知道要解决的问题属于哪一类,则可以找出是否仍有可能榨取很少的额外性能。 1个

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

1, 但正如他们所说,不要过度使用, 过早的优化是万恶之源 ,而没有正当理由的优化也应该得到这个名字。


关于“如何计算” Big O,这是计算复杂性理论的一部分。 对于某些(许多)特殊情况,您可能可以使用一些简单的启发式方法(例如,对嵌套循环乘以循环计数),特别是。 当您想要的只是任何上限估计,而您也不介意它是否过于悲观时-我想这可能是您的问题所在。

如果您真的想回答任何算法的问题,那么您最好的方法就是运用理论。 除了简单的“最坏情况”分析,我发现摊销分析在实践中非常有用。


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

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

假设我们有一个类似( 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)

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


大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表示法很有用,因为它易于使用并且隐藏了不必要的复杂性和细节(对于不必要的某种定义)。 树法是解决分而治之算法复杂性的一种不错的方法。 假设您有一个带有中值过程的quicksort版本,因此每次都将数组拆分为完全平衡的子数组。

现在,构建一个与您使用的所有阵列相对应的树。 在根目录下,您拥有原始数组,在根目录下,有两个子数组,它们是子数组。 重复此操作,直到底部有单个元素数组。

由于我们可以找到O(n)时间的中位数,并在O(n)时间中将数组分为两部分,因此每个节点的工作量为O(k),其中k是数组的大小。 树的每个级别最多包含整个数组,因此每个级别的工作量为O(n)(子数组的大小总计为n,并且由于每个级别有O(k),因此我们可以将其相加) 。 自从我们每次将输入减半后,树中只有log(n)级别。

因此,我们可以通过O(n * log(n))来限制工作量。

但是,Big O隐藏了一些有时我们无法忽略的细节。 考虑使用以下方法计算斐波那契数列

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

并假设a和b是Java中的BigIntegers或可以处理任意大数的东西。 大多数人会说这是O(n)算法,不会退缩。 原因是在for循环中有n次迭代,而O(1)在循环中起作用。

但是斐波那契数很大,第n个斐波那契数在n中是指数的,因此仅存储它就需要n个字节的顺序。 用大整数执行加法将需要O(n)的工作量。 因此,此过程中完成的总工作量为

1 + 2 + 3 + ... + n = n(n-1)/ 2 = O(n ^ 2)

因此,该算法在四基时间运行!


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

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


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

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

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

O(log N )<O( N )<O( N log N )<O( N 2 )<O( N k )<O(e n )<O( n !)


将算法分解为您知道大O表示法的部分,然后通过大O运算符进行组合。 那是我唯一知道的方法。

有关更多信息,请查看该主题的Wikipedia页面


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

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

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

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

时间复杂度不同:

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

  • ...

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

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


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

您的基本工具是决策点及其熵的概念。 决策点的熵是它将为您提供的平均信息。 例如,如果程序包含具有两个分支的决策点,则其熵是每个分支的概率与该分支的逆概率的对数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)排序算法基于索引搜索,则可能是可行的。

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


我会尽力在这里简单地解释它,但要注意,这个主题需要我的学生花几个月的时间才能最终掌握。 您可以在《 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 formpolynomium
  3. 除以多项式的项,然后按增长率对其进行排序。
  4. N接近infinity大时,保持一个增大的值。

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

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

除去所有C常量和冗余部分:

f(N) = 1 + N ^ 1

由于最后一项是当f()接近无穷大(考虑limits )时会增大的项,因此这是BigOh参数,并且sum()函数的BigOh为:

O(N)

有一些技巧可以解决一些棘手的问题:尽可能使用summations

例如,可以使用求和轻松地解决此代码:

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²)

我认为一般来说不太有用,但是为了完整起见,还有一个Big OmegaΩ (它定义了算法复杂度的下限),还有一个Big ThetaΘ (定义了上限和下限)。


熟悉我使用的算法/数据结构和/或快速浏览迭代嵌套分析。 困难在于您可能多次调用库函数-您常常不确定是否有时会不必要地调用该函数或它们正在使用哪种实现。 也许库函数应该具有复杂性/效率度量,无论是Big O还是其他度量标准,都可以在文档中甚至在IntelliSense


让我们从头开始。

首先,接受这样的原理,即可以在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 <n是否为n,从而得出结论,外循环的每次迭代都需要O(n)时间。

外循环的初始化i = 0和条件i <n的第(n + 1)次测试同样花费O(1)时间,可以忽略。 最后,我们观察到我们绕了外循环n次,每次迭代都花费O(n)时间,从而得出总的O(n^2)运行时间。

一个更实际的例子。


除了使用master方法(或其专业之一)之外,我还通过实验测试了我的算法。 这不能证明实现了任何特定的复杂性类,但是可以保证数学分析是适当的。 为了保证这种安全,我将代码覆盖率工具与实验结合使用,以确保我能正确执行所有案例。

举一个非常简单的例子,您想对.NET框架的列表排序速度进行完整性检查。您可以编写类似以下内容的内容,然后在Excel中分析结果以确保它们不超过n * log(n)曲线。

在此示例中,我测量了比较次数,但还是谨慎地检查每种样本量所需的实际时间。但是,那么您必须更加小心,仅在测量算法而不包括测试基础结构中的工件。

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

对于代码A,外部循环将执行n+1一段时间,“ 1”时间表示检查我是否仍满足要求的过程。内循环运行的n次数,n-2时间0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)

对于代码B,尽管内部循环不会介入并执行foo(),但内部循环将执行n次,具体取决于外部循环的执行时间,即O(n)


通常被忽略的是算法的预期行为。它不会改变算法的Big-O,但确实与“过早优化.....”语句有关。

算法的预期行为-非常笨拙-可以预期算法在最有可能看到的数据上运行的速度。

例如,如果要在列表中搜索值,则为O(n),但是如果您知道看到的大多数列表中都有值,则算法的典型行为会更快。

要真正确定下来,您需要能够描述“输入空间”的概率分布(如果您需要对列表进行排序,那么该列表已经被排序的频率是多少?完全颠倒了多少?多数情况下是排序的吗?)知道这一点并不总是可行的,但有时您知道。





performance