大O，你怎么计算/近似呢？

大多数拥有CS学位的人肯定知道Big O代表什么。 它可以帮助我们衡量一个algorithm的效率如何，如果你知道你想要解决的问题在哪个类别中，你可以找出是否仍然可以排除这个额外的性能。 ¹

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

¹ _{但是正如他们所说的那样，不要过头， 不成熟的优化是万恶之源 ，没有正当理由的优化也应该得到这个名称。}

Answer 1

我是当地大学的数据结构和algorithm课程的助教。 我会尽我所能在这里简单地解释一下，但要注意的是，这个话题让我的学生们花了好几个月的时间才终于掌握了。 您可以在Java书籍的“ 数据结构和algorithm ”第2章中find更多信息。

---

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

作为一本“食谱”，为了从一段代码中获得BigOh ，你首先需要意识到，你正在创build一个math公式来计算在input一定大小的情况下执行多less个计算步骤。

目的很简单：从理论angular度比较algorithm，而不需要执行代码。 步数越less，algorithm越快。

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

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 } 

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

 Number_Of_Steps = f(N) 

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

 Number_Of_Steps = f(data.length) 

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

有很多方法来计算BigOh。 从这一点开始，我们将假设每一个不依赖于input数据大小的句子都采用一个常数C计算步骤。

我们将添加该函数的单个步骤数量，局部variables声明和返回语句都不依赖于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的主体被执行了多less次，你需要通过查看代码做什么来计算它。 为了简化计算，我们忽略了for语句的variables初始化，条件和增量部分。

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

1. 拿走所有的常数C
2. 从f()得到standard form的polynomium 。
3. 划分多项式的条件并按增长率sorting。
4. 当N接近infinity时，保持越大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的大小无关。

关于第一句的陈述是棘手的。 当索引以2 * N结尾时，增量由2来完成。 这意味着第一个执行只有N步，我们需要将计数除以二。

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

第二句更加棘手，因为它取决于i的价值。 看看：索引我取的值为：0,2,4,6,8，…，2 * N，第二个得到执行：N的第一个，N – 2的第二，N – 4第三…直到N / 2阶段，第二个永不执行。

在公式上，这意味着：

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

再次，我们正在计算步数 。 根据定义，每一个总和应该总是从一开始，以一个大于或等于一的数字结束。

 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向上时，内部Summation以负数结束！ 这是不可能的和错误的。 我们需要把两者的总和分开，这是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 ，所以内层将不会被执行，并且我们假设它的主体的执行复杂度是恒定的。

现在可以使用一些身份规则来简化总和：

1. 求和（从1到N）（C）= N * C
2. 总和（W从1到N）（A（+/-）B）=总和（W从1到N）（A）（+/-）总和（w从1到N）
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

大O给出algorithm的时间复杂度的上限。 它通常与处理数据集（列表）一起使用，但可以在别处使用。

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

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

 int array[n]; 

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

 x = array[0]; 

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

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

这是O（n），因为我们至多不得不查看整个列表来find我们的号码。 大O仍然是O（n），尽pipe我们可能会首先尝试并通过循环运行一次，因为Big-O描述了一个algorithm的上界（Ω是下界，θ是下界） 。

当我们得到嵌套循环：

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

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

这只是表面上的瑕疵，但是当您分析更复杂的algorithm时，涉及certificate的复杂math将发挥作用。 希望这至less能让你熟悉基础知识。

Answer 3

在了解如何针对特定问题计算大时间的情况下非常有用，了解一些常规情况可以帮助您在algorithm中做出决定。

以下是一些最常见的情况，从http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions中解除：;

O（1） – 确定一个数字是偶数还是奇数; 使用恒定大小的查找表或散列表

O（logn） – 使用二分search查找sorting数组中的项目

O（n） – 在未sorting列表中查找项目; 增加两个n位数字

O（n ² ） – 用简单的algorithm乘以两个n位数字; 增加两个n×nmatrix; 冒泡sorting或插入sorting

O（n ³ ） – 用简单的algorithm乘以两个n×nmatrix

O（c ⁿ ） – 使用dynamic规划查找旅行商问题的（确切的）解决scheme; 用暴力来确定两个逻辑语句是否相等

O（n！） – 通过蛮力search解决旅行商问题

O（n ⁿ ） – 通常用来代替O（n！）来得到渐近复杂度的简单公式

Answer 4

小提醒： big O表示法用来表示渐近复杂性（即当问题的大小增长到无穷大时）， 并隐藏一个常量。

这意味着在O（n）中的algorithm和O（n ² ）中的algorithm之间，最快并不总是第一个（尽pipe总是存在n的值，使得对于大于n的问题，第一个algorithm是最快的）。

请注意，隐藏的常量很大程度上取决于实现！

另外，在某些情况下，运行时不是input大小 n的确定性函数。 例如，使用快速sorting进行sorting：对n个元素数组进行sorting所需的时间不是一个常量，而是取决于数组的起始configuration。

有不同的时间复杂性：

• 最坏的情况（通常是最简单的，尽pipe并不总是很有意义）

• 平均情况下（通常很难弄清楚…）

• …

一个很好的介绍是R. Sedgewick和P. Flajolet 的“algorithm分析入门” 。

正如你所说， premature optimisation is the root of all evil ，并且（如果可能的话）在优化代码时确实应该始终使用分析 。 它甚至可以帮助您确定algorithm的复杂性。

Answer 5

在这里看到答案，我想我们可以得出结论，我们大多数人的确通过观察algorithm来确定algorithm的顺序，并且使用常识，而不是像在大学时那样用主方法来计算algorithm。 有了这个说法，我必须补充一点，就是教授也鼓励我们（后来）真正考虑这个问题，而不是去计算它。

另外我想补充说明如何完成recursionfunction ：

假设我们有一个函数（ scheme代码 ）：

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

recursion地计算给定数量的阶乘。

第一步是只在这种情况下尝试确定函数主体的性能特征， 在主体中没有什么特别的，只是乘法（或返回值1）。

所以身体的performance是：O（1） （常数）。

接下来尝试确定recursion调用的数量 。 在这种情况下，我们有n-1个recursion调用。

所以recursion调用的性能是：O（n-1） （顺序是n，因为我们扔掉了不重要的部分）。

然后把这两个放在一起，然后你就得到了整个recursion函数的性能：

1 *（n-1）= O（n）

---

彼得 ，回答你提出的问题; 我在这里描述的方法实际上处理得很好。 但请记住，这仍然是一个近似值，而不是一个完整的math正确的答案。 这里所描述的方法也是我们在大学教过的方法之一，如果我没有记错的话，这个方法比我在这个例子中使用的阶乘要高得多。
当然，这一切都取决于你可以估计函数主体的运行时间和recursion调用的次数，但是对于其他方法也是如此。

Answer 6

如果你的成本是一个多项式，只保留最高阶项，没有乘数。 例如：

O（n / 2 + 1）*（n / 2））= O（n 2/4 + n / 2）= O（n 2/4）= O

这不适用于无限的系列，介意你。 一般情况下没有单一的配方，但对于一些常见情况，以下不等式适用：

O（log N ）<O（ N ）<O（ N log N ）<O（ N ² ）<O（ N ^k ）<O（e ⁿ ）<O（ n ！）

Answer 7

我从信息的angular度思考这个问题。 任何问题都包括学习一定数量的比特。

你的基本工具是决策点和它们的熵的概念。 决策点的熵是它会给你的平均信息。 例如，如果一个程序包含一个带有两个分支的决策点，那么它的熵就是每个分支的概率乘以该分支逆概率log ₂的总和。 这是通过执行这个决定你学到多less。

例如，具有两个等分可能的分支的if语句具有1/2 * log（2/1）+ 1/2 * log（2/1）= 1/2 * 1 + 1/2 * 1 = 1，所以它的熵是1位。

假设你正在searchN个项目的表，如N = 1024。 这是一个10位的问题，因为log（1024）= 10位。 因此，如果您可以使用具有相同可能结果的IF语句进行search，则需要10个决定。

这就是你用二进制search得到的。

假设你正在进行线性search。 你看第一个元素，并问是否是你想要的。 它的概率是1/1024，而1023/1024它不是。 该决定的熵是1/1024 * log（1024/1）+ 1023/1024 * log（1024/1023）= 1/1024 * 10 + 1023/1024 *约0 =约0.01位。 你学到的很less！ 第二个决定并不好。 这就是线性search速度如此之慢的原因。 事实上，你需要学习的位数是指数的。

假设你在做索引。 假设表被预先分类到很多仓，并且你使用键中的所有位中的一些来直接索引表项。 如果有1024个分箱，则对于所有1024个可能的结果，熵是1/1024 * log（1024）+ 1/1024 * log（1024）+ …。 这是1024个结果的1/1024 * 10倍，或者是那个索引操作的10位熵。 这就是为什么索引search很快。

现在想想sorting。 你有N个项目，你有一个列表。 对于每个项目，您必须search项目在列表中的位置，然后将其添加到列表中。 所以sorting大致需要N倍于底层search的步骤数量。

所以基于具有大致相等的可能结果的二元决策进行sorting都需要大约O（N log N）个步骤。 如果基于索引search，则O（N）sortingalgorithm是可能的。

我发现几乎所有的algorithm性能问题都可以通过这种方式来看待。

Answer 8

让我们从头开始。

首先，接受一个简单的数据操作可以在O(1)时间内完成的原则，即在与input大小无关的时间内完成。 C中的这些基本操作由…组成

1. 算术运算（例如+或％）。
2. 逻辑运算（例如&&）。
3. 比较操作（例如，<=）。
4. 结构访问操作（例如像A [i]的数组索引，或者使用 – >运算符的指针）。
5. 简单的赋值，如将值复制到variables中。
6. 调用库函数（例如，scanf，printf）。

这个原理的理由需要详细研究典型计算机的机器指令（原始步骤）。 每个描述的操作都可以用less量的机器指令完成; 通常只需要一个或两个指令。 因此，C语言中的几种语句可以在O(1)时间内执行，也就是在一定的时间内独立于input。 这些简单的包括

1. 在expression式中不涉及函数调用的分配语句。
2. 读取语句。
3. 编写不需要函数调用来评估参数的语句。
4. 跳转语句中断，继续，跳转和返回expression式，其中expression式不包含函数调用。

在C中，许多for循环是通过将索引variables初始化为某个值并在该循环中每次将该variables递增1而形成的。 当索引达到某个限制时，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; } 

使用索引variablesi。 它在循环中每次增加1，迭代在到达n-1时停止。

但是，目前，只关注for循环的简单forms，其中最终值和初始值之间的差值除以索引variables的增量，告诉我们循环多less次 。 这个计数是确切的，除非有办法通过跳转语句退出循环; 在任何情况下，它都是迭代次数的上限。

例如，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）时间，以便首次比较循环索引与极限 ，因为我们testing的时间比我们循环的多一倍。 但是，除非可以执行循环零次，否则初始化循环并testing一次限制的时间是一个低阶项，可以通过求和规则删除。

---

现在考虑这个例子：

 (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，并且在每次迭代中testing是否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）的运行时间。

很less（除非你正在编写一个具有广泛的基础库的平台（比如.NET BCL或者C ++的STL），否则你将遇到任何比查看你的循环更困难的事情（对于语句，while，goto，等等…）

Answer 11

把algorithm分解成你认识大O的符号，并通过大O操作符合并。 这是我知道的唯一方法。

欲了解更多信息，请查看关于这个主题的维基百科页面 。

Answer 12

熟悉我使用的algorithm/数据结构和/或迭代嵌套的快速浏览分析。 难点是当你调用一个库函数时，可能会多次 – 你可能经常不确定是否在不必要的时候调用函数，或者他们正在使用什么实现。 也许库函数应该有一个复杂度/效率度量，无论是大O还是其他度量，这在文档中甚至IntelliSense中都是可用的。

Answer 13

一般而言，我认为不太有用，但为了完整起见，还有一个Big OmegaΩ ，它定义了一个algorithm复杂度的下限， Big Ta（θ ）定义了一个上下限。

Answer 14

大O符号是有用的，因为它很容易处理和隐藏不必要的复杂性和细节（一些不必要的定义）。 树algorithm是计算分治algorithm复杂性的一个好方法。 假设你有一个中间过程的quicksort版本，所以你每次都把数组分成完全平衡的子arrays。

现在build立一个对应于你所使用的所有数组的树。 在根目录你有原始数组，根有两个孩子是子数组。 重复这个，直到你在底部有单个元素数组。

由于我们可以在O（n）时间内find中值，并在O（n）时间内将数组分成两部分，所以在每个节点上完成的工作是O（k），其中k是数组的大小。 树的每一层都包含（最多）整个数组，因此每层的工作是O（n）（子arrays的大小合计为n，因为每层都有O（k），所以我们可以把它加起来） 。 每次我们将input减半时，树中只有log（n）级别。

因此，我们可以通过O（n * log（n））来限制工作量。

但是，大澳隐藏了一些我们有时不能忽视的细节。 考虑计算Fibonacci序列

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

让我们假设a和b是Java中的BigInteger，或者可以处理任意数量的东西。 大多数人会说这是一个没有退缩的O（n）algorithm。 推理是你在循环中有n次迭代，而O（1）在循环中工作。

但是斐波那契数是很大的，第n个斐波那契数在n中是指数的，所以只存储它将会有n个字节的顺序。 用大整数进行加法将需要O（n）个工作量。 所以在这个程序中完成的工作总量是

1 + 2 + 3 + … + n = n（n-1）/ 2 = O（n ^ 2）

所以这个algorithm在四倍时间运行！

Answer 15

至于“你怎么计算”大O，这是计算复杂性理论的一部分。 对于一些（很多）特殊情况，你可能会有一些简单的启发式（比如嵌套循环的循环计数）。 当你想要的是任何上限的估计，你不介意是否过于悲观 – 我猜可能是你的问题。

如果你真的想为任何algorithm回答你的问题，你所能做的最好的就是应用这个理论。 除了简单的“最坏情况”分析，我发现摊销分析在实践中非常有用。

Answer 16

对于第一种情况，内部循环执行的次数是ni次，所以执行总次数是ni从0到n-1的总和（因为低于，不低于或等于）。 最后得到n*(n + 1) / 2 ，所以O(n²/2) = O(n²) 。

对于第二个循环， i在外部循环中包含0和n之间; 那么当j严格大于n ，执行内部循环，这是不可能的。

Answer 17

除了使用主方法（或其专业之一）之外，我还通过实验testing了我的algorithm。 这不能certificate任何特定的复杂等级是成立的，但它可以保证math分析是合适的。 为了保证这一点，我使用了代码覆盖工具和我的实验结合起来，以确保我正在运用所有的案例。

作为一个非常简单的例子，你想对.NET框架的列表sorting的速度做一个合理的检查。 你可以写下如下的内容，然后在Excel中分析结果，以确保它们不超过n * log（n）曲线。

在这个例子中，我测量了比较的次数，但是仔细检查每个样本大小所需的实际时间。 但是，您必须更加小心，您只是在测量algorithm，而不包括来自testing基础架构的工件。

 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 18

不要忘记，如果存储资源有限，也可以考虑空间复杂性，这也可能是一个值得关注的问题。 因此，例如，您可能会听到有人想要一个恒定的空间algorithm，这基本上是一种说法，该algorithm所占用的空间量不取决于代码中的任何因素。

有时复杂性可能来自于多less次被调用，多久执行一次循环，多久分配一次内存等等，这些都是回答这个问题的另一部分。

最后，大O可用于最糟糕的情况，最好的情况和分期付款的情况，通常最糟糕的情况是用来描述algorithm可能有多糟糕。

Answer 19

经常被忽视的是algorithm的预期行为。 它不会改变algorithm的Big-O ，但它确实涉及到“不成熟的优化……”

您的algorithm的期望行为是 – 非常愚蠢 – 您可以期待您的algorithm能够处理最有可能看到的数据的速度。

例如，如果你在列表中search一个值，那么它就是O（n），但是如果你知道你看到的大多数列表都有你的价值，那么你的algorithm的典型行为就会更快。

要真正明白它，你需要能够描述你的“input空间”的概率分布（如果你需要对列表进行sorting，这个列表已经被sorting了多less次？多长时间一次是完全颠倒的？往往是大多数sorting？）你知道这并不总是可行的，但有时候你会这样做。

Answer 20

对于代码A，外部循环将执行n + 1次，'1'时间意味着检查我是否仍然符合要求的过程。 因此，0 + 2 + … +（n-2）+ n =（0 + n）（n + 1）/ 2 = O（n 2）。

对于代码B，虽然内部循环不会介入并执行foo（），但内部循环将执行n次，取决于外部循环执行时间，即O（n）

Answer 21

I don't know how to programmatically solve this, but the first thing people do is that we sample the algorithm for certain patterns in the number of operations done, say 4n^2 + 2n + 1 we have 2 rules:

1. If we have a sum of terms, the term with the largest growth rate is kept, with other terms omitted.
2. If we have a product of several factors constant factors are omitted.

If we simplify f(x), where f(x) is the formula for number of operations done, (4n^2 + 2n + 1 explained above), we obtain the big-O value [O(n^2) in this case]. But this would have to account for Lagrange interpolation in the program, which may be hard to implement. And what if the real big-O value was O(2^n), and we might have something like O(x^n), so this algorithm probably wouldn't be programmable. But if someone proves me wrong, give me the code . 。 。 。

Answer 22

great question!

If you're using the Big O, you're talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

---

Ok, so now what do we mean by "best-case" and "worst-case" complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the worst case is when we decide to search for the last element of the array as this would take as many steps as there are items in the array. The best case would be when we search for the first element since we would be done after the first check.

The point of all these adjective -case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

Sorry this is so poorly written and lacks much technical information. But hopefully it'll make time complexity classes easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in trivial cases and what input would result in worst-cases.