大O,你如何计算/近似它？

Question

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

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

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

Answer 1

我是当地大学数据结构和算法课程的助理教授.我将尽力以简单的术语在这里解释,但请注意,这个主题需要我的学生几个月才能最终掌握.您可以在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()获得polynomium它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,增量由两个完成.这意味着第一个for只执行N步骤,我们需要将计数除以2.

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

句号码2是更加棘手,因为它取决于价值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²)

Answer 2

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平方.

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

Answer 3

虽然知道如何找出特定问题的大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!)来推导渐近复杂度的简单公式

Answer 4

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

这意味着在O(n)中的算法和O(n ²)中的算法之间,最快的并不总是第一个(尽管总是存在n的值,使得对于大小> n的问题,第一个算法是最快的).

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

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

有不同的时间复杂性:

• 最坏的情况(通常最简单的解决,但并不总是非常有意义)

• 平均情况(通常更难以弄清楚...)

• ...

一个很好的介绍是R. Sedgewick和P. Flajolet 的算法分析导论.

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

Answer 5

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

另外我想补充它是如何为递归函数完成的:

假设我们有一个像(方案代码)这样的函数:

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

彼得,回答你提出的问题; 我在这里描述的方法实际上处理得很好.但请记住,这仍然是一个近似值,而不是一个完整的数学上正确的答案.这里描述的方法也是我们在大学教授的方法之一,如果我没记错的是用于比我在本例中使用的因子更高级的算法.
当然,这完全取决于你能够估计函数体的运行时间和递归调用的数量,但对于其他方法也是如此.

Answer 6

如果您的成本是多项式,只需保留最高阶项,而不是其乘数.例如:

O((N/2 + 1)*(N/2))= O(N ² /4 + N/2)= O(N ² /4)= O(N ²)

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

O(log N)<O(N)<O(N log N)<O(N ²)<O(N ^k)<O(e ⁿ)<O(n!)

Answer 7

我从信息的角度思考问题.任何问题都包括学习一定数量的比特.

您的基本工具是决策点及其熵的概念.决策点的熵是它给你的平均信息.例如,如果程序包含具有两个分支的决策点,则其熵是每个分支的概率乘以该分支的反概率的log ₂的总和.这就是你通过执行该决定所学到的东西.

例如,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个箱,则熵为1/1024*log(1024)+ 1/1024*log(1024)+ ...对于所有1024个可能的结果.对于该一个索引操作,这是1024个结果的1/1024*10倍,或10个比特的熵.这就是为什么索引搜索速度很快的原因.

现在考虑排序.您有N个项目,并且您有一个列表.对于每个项目,您必须搜索项目在列表中的位置,然后将其添加到列表中.因此,排序大约是底层搜索步数的N倍.

因此,基于具有大致相同可能结果的二元决策的排序都需要O(N log N)步骤.如果基于索引搜索,则可以使用O(N)排序算法.

我发现几乎所有的算法性能问题都可以用这种方式来看待.

Answer 8

让我们从头开始.

首先,接受这样的原则:对数据的某些简单操作可以及时完成O(1),即与输入的大小无关的时间.C中的这些原始操作包括

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

该原理的理由需要详细研究典型计算机的机器指令(原始步骤).可以用一些少量的机器指令完成所描述的每个操作; 通常只需要一两条指令.因此,C中的几种语句可以及时执行O(1),即,在与输入无关的某些恒定时间内执行.这些简单包括

1. 在表达式中不涉及函数调用的赋值语句.
2. 阅读陈述.
3. 编写不需要函数调用来评估参数的语句.
4. jump语句break,continue,goto和return表达式,其中expression不包含函数调用.

在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.它在循环周围每次递增1,当我达到n - 1时迭代停止.

但是,暂时关注for循环的简单形式,其中最终值和初始值之间的差异除以索引变量递增的量告诉我们循环循环的次数.这个计数是准确的,除非有办法通过跳转语句退出循环; 它是任何情况下迭代次数的上限.

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

在最简单的情况下,循环体中花费的时间对于每次迭代是相同的,我们可以将体的大上限乘以循环周围的次数.严格地说,我们必须添加O(1)时间来初始化循环索引和O(1)时间,以便首次将循环索引与限制进行比较,因为我们测试的时间比循环循环时多一个.但是,除非可以执行循环零次,否则初始化循环和测试限制一次的时间是一个低阶项,可以通过求和规则删除.

现在考虑这个例子:

(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)时间.因此,我们可以忽略增加i的O(1)时间并测试每次迭代中是否i <n,得出结论外循环的每次迭代花费O(n)时间.

外循环的初始化i = 0和条件i <n的(n + 1)st测试同样需要O(1)时间并且可以忽略.最后,我们观察到我们绕过外循环n次,每次迭代花费O(n)时间,给出总 O(n^2)运行时间.

一个更实际的例子.

Answer 9

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

与仅研究代码相比,这有几个优点.首先,您可以看到您是否处于运行时间接近其渐近顺序的范围内.此外,您可能会发现某些您认为是O(x)顺序的代码实际上是订单O(x ^ 2),例如,因为在库调用中花费的时间.

Answer 10

基本上90%的时间只是分析循环.你有单,双,三嵌套循环吗？你有O(n),O(n ^ 2),O(n ^ 3)运行时间.

很少(除非你正在编写一个具有广泛基础库的平台(例如,.NET BCL或C++的STL),否则你会遇到比查看循环更困难的任何事情(对于语句,同时,goto,等等...)

Answer 11

Big O表示法很有用,因为它易于使用并隐藏不必要的复杂性和细节(对于某些不必要的定义).计算分而治之算法复杂性的一种好方法是树方法.假设您有一个带有中间过程的快速排序版本,因此您每次都将阵列拆分为完美平衡的子阵列.

现在构建一个与您使用的所有数组相对应的树.在根处有原始数组,根有两个子数组,即子数组.重复此操作,直到底部有单个元素数组.

由于我们可以在O(n)时间内找到中值并在O(n)时间内将数组分成两部分,因此在每个节点处完成的工作是O(k),其中k是数组的大小.树的每个级别(最多)包含整个数组,因此每个级别的工作是O(n)(子数组的大小加起来为n,因为我们每个级别有O(k),我们可以添加它) .因为每次我们将输入减半,树中只有log(n)级别.

因此,我们可以通过O(n*log(n))将工作量上限.

但是,Big O隐藏了一些我们有时不能忽视的细节.考虑使用计算Fibonacci序列

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)

所以这个算法在四维时间运行!

Answer 12

我认为通常不太有用,但为了完整起见,还有一个BigOmegaΩ,它定义了算法复杂度的下限,还有一个BigThetaΘ,它定义了一个上限和下限.

Answer 13

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

Answer 14

将算法分解为您知道大O符号的片段,并通过大O运算符进行组合.这是我所知道的唯一方式.

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

Answer 15

我想从一个稍微不同的方面来解释 Big-O。

Big-O 只是比较程序的复杂性，这意味着当输入增加时它们的增长速度有多快，而不是执行操作所花费的确切时间。

恕我直言，在大 O 公式中，您最好不要使用更复杂的方程（您可能只坚持使用下图中的方程。）但是您仍然可以使用其他更精确的公式（例如 3^n、n^3、.. .) 但不仅如此，有时可能会产生误导！因此最好保持尽可能简单。

我想再次强调，在这里我们不想得到我们算法的精确公式。我们只想展示当输入增长时它如何增长，并在这个意义上与其他算法进行比较。否则，您最好使用不同的方法，例如基准测试。

Answer 16

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

如果你真的想回答任何算法的问题,你可以做的最好的是应用理论.除了简单的"最坏情况"分析,我发现摊销分析在实践中非常有用.

Answer 17

对于第一种情况,内循环执行n-i次数,因此执行的总次数是i从的0开始n-1(因为低于,不低于或等于)n-i.你终于得到了n*(n + 1) / 2,所以O(n²/2) = O(n²).

对于第二个循环,在外循环i之间0并n包括在内; 然后,当j严格大于时n,执行内循环,这是不可能的.

Answer 18

除了使用主方法(或其专业化之一)之外,我还通过实验测试算法.这不能证明任何特定的复杂性类别都可以实现,但它可以确保数学分析是合适的.为了帮助解决这个问题,我将代码覆盖工具与我的实验结合使用,以确保我能够运用所有案例.

作为一个非常简单的例子,你想要对.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);

Answer 19

不要忘记还考虑到空间复杂性，如果内存资源有限，这也可能是一个令人担忧的问题。例如，您可能会听到有人想要一个恒定空间算法，这基本上是一种说法，即算法占用的空间量不取决于代码中的任何因素。

有时，复杂性可能来自某事物被调用的次数、循环执行的频率、内存分配的频率等等，这是回答这个问题的另一部分。

最后，大 O 可用于最坏情况、最好情况和摊销情况，通常最坏情况用于描述算法可能有多糟糕。

Answer 20

首先，公认的答案是试图解释漂亮的花哨的东西，
但我认为，故意使Big-Oh 复杂化并不是
程序员（或者至少像我这样的人）寻找的解决方案。

大哦（简而言之）

function f(text) {
  var n = text.length;
  for (var i = 0; i < n; i++) {
    f(text.slice(0, n-1))
  }
  // ... other JS logic here, which we can ignore ...
}

上面的大哦是 f(n) = O(n!)，其中n表示number输入集中的项目，f表示operation每个项目的完成情况。

Big-Oh 表示法是算法复杂度的渐近上限。
在编程中：对于输入的大小，假设的最坏情况所花费的时间，
或假设的最大逻辑重复计数。

计算

请记住（根据上述含义）；我们只需要受N（输入大小）影响的最坏情况时间和/或最大重复次数， 然后再看一下（接受的答案）示例：

for (i = 0; i < 2*n; i += 2) {  // line 123
    for (j=n; j > i; j--) {     // line 124
        foo();                  // line 125
    }
}

1. 从这个搜索模式开始：

   • 找到N导致重复行为的第一行，
   • 或者导致执行的逻辑增加，
   • 但无论是否恒定，请忽略该行之前的任何内容。

2. 看来第 23 行就是我们正在搜索的内容;-)

   • 乍一看，线路似乎有2*n最大循环。
   • 但再看一遍，我们看到了i += 2（并且跳过了一半）。
   • 因此，最大重复次数就是n，将其写下来，f(n) = O( n 但不要关闭括号。

3. 重复搜索直到方法结束，并找到与我们的搜索模式匹配的下一行，这里是第 124 行

   • 这很棘手，因为奇怪的条件和反向循环。
   • 但记住我们只需要考虑最大重复次数（或最坏情况下花费的时间）。
   • 这就像说“反向循环j以 开始j=n，我说得对吗？是的，n似乎是最大可能的重复次数”，所以：
     • 添加n到之前写下的末尾，
     • 但就像“ ( n ”而不是“ + n”（因为这是在上一个循环内），
     • 仅当我们找到前一个循环之外的内容时才关闭括号。

搜索完成！为什么？因为第 125 行（或之后的任何其他行）与我们的搜索模式不匹配。
我们现在可以关闭任何括号（在我们的记录中左开），结果如下：

f(n) = O( n( n ) )

尝试进一步缩短“ n( n )”部分，例如：

• n(n)=n*n
• = n ²
• 最后，只需用 Big Oh 表示法将其包装起来，例如O(n ² )或 O(n^2) 而不进行格式化。