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

熟悉我使用的算法/数据结构和/或对迭代嵌套的快速浏览分析。困难在于当你调用库函数时，可能多次——你通常不确定是否有时不必要地调用了该函数，或者它们使用的是什么实现。也许库函数应该有一个复杂性/效率度量，无论是大O还是其他度量，在留档甚至智能感知中可用。

将算法分解成你知道的大O符号，并通过大O运算符组合。这是我知道的唯一方法。

有关详细信息，请检查主题上的维基百科页面。

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描述了算法的上界（ω表示下界，θ表示紧界）。

当我们进入嵌套循环时：

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

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

这只是表面，但是当你开始分析更复杂的算法时，涉及证明的复杂数学就会发挥作用。希望这至少能让你熟悉基础知识。

看到这里的答案，我想我们可以得出结论，我们大多数人确实通过寻找来近似算法的顺序，并使用常识来计算它，例如，我们在大学时认为的主方法。话虽如此，我必须补充一点，即使是教授也鼓励我们（后来）实际认为，而不仅仅是计算它。

我还想补充一下它是如何为递归函数完成的：

假设我们有一个像（方案代码）这样的函数：

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

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

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

所以身体的表现为：O（1）（常量）。

接下来尝试为递归调用数确定this。在这种情况下，我们有n-1个递归调用。

所以递归调用的性能为：O（n-1）（顺序是n，因为我们丢弃了无关紧要的部分）。

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

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

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

大O表示法很有用，因为它易于使用并隐藏了不必要的复杂性和细节（对于一些不必要的定义）。解决分而治之算法复杂性的一个好方法是树方法。假设你有一个带有中值过程的快速排序版本，所以你每次都将数组拆分为完美平衡的子数组。

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

由于我们可以在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中的大整数或可以处理任意大数的东西。大多数人会毫不犹豫地说这是一个O（n）算法。理由是你在for循环中有n次迭代，O（1）在循环中工作。

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

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

所以这个算法运行在四进制时间！

基本上90%的时间都在分析循环。你有单、双、三嵌套循环吗？你有O（n）、O（n^2）、O（n^3）运行时间。

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

小提示：big O符号用于表示渐近复杂性（即，当问题的大小增长到无穷大时），和它隐藏了一个常数。

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

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

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

有不同的时间复杂度：

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

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

• …

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

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

除了使用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 integersvoid 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 checkfor( int n = 0; n<1000; n++ )DoTest(n);

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

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

O（1）-确定数字是偶数还是奇数；使用恒定大小的查找表或哈希表

O（logns）-使用二分搜索在排序数组中查找项目

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

O（n²）-用简单算法将两个n位数相乘；添加两个n×n矩阵；冒泡排序或插入排序

O（n³）-用简单算法将两个n×n矩阵相乘

O（cⁿ）-使用动态规划找到旅行推销员问题的（精确）解决方案；使用蛮力确定两个逻辑语句是否等价

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

O（nⁿ）-通常用来代替O（n！）来推导渐近复杂度的简单公式

我认为一般不太有用，但为了完整起见，还有一个大欧米茄Ω，它定义了算法复杂性的下限，还有一个大Thetaθ，它定义了上限和下限。

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

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

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

如果你想根据经验而不是通过分析代码来估计代码的顺序，你可以坚持一系列递增的n值并为你的代码计时。在对数刻度上绘制你的计时。如果代码是O（x^n），则值应该落在斜率n的线上。

这比仅仅研究代码有几个好处。首先，你可以看到你是否在运行时接近其渐近顺序的范围内。此外，你可能会发现，一些你认为是O（x）阶的代码实际上是O（x^2）阶，例如，因为花在库调用上的时间。

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

你的基本工具是决策点及其熵的概念。决策点的熵是它将给你的平均信息。例如，如果一个程序包含一个有两个分支的决策点，它的熵是每个分支的概率乘以该分支逆概率的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*about 0=about.01 bit。你学到的东西很少！第二个决策也没好到哪里去。这就是线性搜索如此慢的原因。事实上，你需要学习的位数是指数级的。

假设你正在进行索引。假设表被预先排序到很多箱中，并且你使用键中的一些位直接索引到表条目。如果有1024个箱，对于所有1024个可能的结果，熵是1/1024*log（1024）+1/1024*log（1024）+…。这是1/1024*10乘以1024个结果，或者一次索引操作的熵是10位。这就是索引搜索快的原因。

现在考虑排序。你有N个项目，你有一个列表。对于每个项目，你必须搜索该项目在列表中的位置，然后将其添加到列表中。所以排序大约需要N倍于底层搜索的步骤数。

因此，基于具有大致相等可能结果的二元决策的排序都需要大约O（N log N）步。如果基于索引搜索，O（N）排序算法是可能的。

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

经常被忽视的是算法的预计行为。它不会改变你算法中的Big-O，但它确实与语句“过早优化”有关。

你的算法的预期行为是——非常愚蠢——你可以期望你的算法在你最有可能看到的数据上工作的速度。

例如，如果你在列表中搜索一个值，它是O（n），但如果你知道你看到的大多数列表都有你的值，你的算法的典型行为会更快。

要真正确定它，你需要能够描述你的“输入空间”的概率分布（如果你需要对一个列表进行排序，这个列表已经被排序的频率是多少？它完全颠倒的频率是多少？它大多被排序的频率是多少？）你知道这一点并不总是可行的，但有时你会这样做。

至于“你如何计算”大O，这是计算复杂性理论的一部分。对于一些（许多）特殊情况，你可能可以得到一些简单的启发式方法（比如嵌套循环的循环计数相乘），特别是当你想要的只是任何上限估计，你不介意它是否太悲观——我想这可能就是你的问题所在。

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

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

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

注意，这对无穷级数不起作用。一般情况下没有单一的配方，尽管对于一些常见情况，以下不等式适用：

O（logN）N）N logN）N²）N^k）n）n！）

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

对于第二个循环，i介于0和n之间，包括在外循环中；然后当j严格大于n时执行内循环，这是不可能的。

我将尽我所能在这里用简单的术语解释它，但要注意，这个主题需要我的学生几个月才能最终掌握。你可以在第0本书的第2章找到更多信息。

没有机械程序可以用来获取BigOh。

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

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

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

int sum(int* data, int N) {int result = 0;               // 1
for (int i = 0; i < N; i++) { // 2result += 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的计算步骤。

我们将添加函数的单个步数，局部变量声明和返回语句都不依赖于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) {  // 1for (j=n; j > i; j--) {     // 2foo();                  // 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开始，并以大于或等于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 from 1 to N）（w*C）=C*求和（w from 1 to 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²)

对于代码A，外部循环将执行n+1次，'1'时间表示检查i是否仍然满足要求的过程。内部循环运行n次，n-2次……因此，0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)。

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

我不知道如何以编程方式解决这个问题，但人们要做的第一件事是，我们对算法中的某些模式进行采样，比如4n^2+2n+1，我们有2个规则：

1. 如果我们有一个项和，则保留增长率最大的项，省略其他项。
   
2. 如果我们有几个因子的乘积，则省略常数因子。

如果我们简化f（x），其中f（x）是完成操作次数的公式，（上面解释的4n^2+2n+1），我们得到大O值[在这种情况下是O（n^2）]。但这必须考虑程序中的拉格朗日插值，这可能很难实现。如果真正的大O值是O（2^n），我们可能有类似于O（x^n）的东西，所以这个算法可能无法编程。但是如果有人证明我错了，给我代码 . . . .

让我们从头开始。

首先，接受这样一个原则，即对数据的某些简单操作可以在O(1)时间内完成，也就是说，在与输入大小无关的时间内完成。C中的这些原始操作包括

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

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

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

在C中，许多for循环是通过将索引变量初始化为某个值和每次循环时将该变量递增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;}

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

但是，目前，请关注简单的for循环形式，其中最终值和初始值之间的差异，除以索引变量递增的量，告诉我们我们在循环中循环了多少次。该计数是准确的，除非有方法通过跳转语句退出循环；无论如何，它是迭代次数的上限。

例如，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）时间限制，因为我们测试的时间比循环的时间多。但是，除非可以执行循环零次，初始化循环和测试的时间极限一次是一个低阶项，可以被求和规则丢弃。

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

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