熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于，当您调用一个库函数时，可能会多次调用—您常常不确定是否在不必要的时候调用了函数，或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量，无论是大O还是其他度量，都可以在文档或智能感知中得到。

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

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

大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)因为我们最多要遍历整个列表才能找到我们要的数。大O仍然是O(n)，即使我们可能在第一次尝试中找到我们的数字并运行一次循环，因为大O描述了算法的上界(omega是下界，theta是紧界)。

当我们讲到嵌套循环时:

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

这是O(n²)因为对于外层循环的每一次循环(O(n))我们都必须再次遍历整个列表，所以n乘以后只剩下n²。

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

看到这里的答案，我想我们可以得出这样的结论:我们大多数人确实通过观察它和使用常识来近似算法的顺序，而不是像我们在大学里认为的那样用主方法来计算它。 说了这么多，我必须补充一点，即使教授也鼓励我们(后来)实际思考，而不是仅仅计算。

我还想补充一下如何对递归函数进行处理:

假设我们有这样一个函数(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, to answer your raised issues; the method I describe here actually handles this quite well. But keep in mind that this is still an approximation and not a full mathematically correct answer. The method described here is also one of the methods we were taught at university, and if I remember correctly was used for far more advanced algorithms than the factorial I used in this example. Of course it all depends on how well you can estimate the running time of the body of the function and the number of recursive calls, but that is just as true for the other methods.

大O符号很有用，因为它很容易使用，并且隐藏了不必要的复杂性和细节(对于一些不必要的定义)。求解分治算法复杂性的一种好方法是树法。假设你有一个带有中值过程的快速排序版本，所以你每次都将数组分割成完美平衡的子数组。

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

由于我们可以在O(n)时间内找到中位数，并在O(n)时间内将数组分成两部分，因此在每个节点上所做的功为O(k)，其中k是数组的大小。树的每一层都包含(最多)整个数组，所以每层的功是O(n)(子数组的大小加起来是n，因为每层有O(k)，我们可以把它加起来)。树中只有log(n)层，因为每次我们将输入减半。

因此，我们可以将功的上限设为O(n*log(n))。

然而，大O隐藏着一些我们有时不能忽视的细节。考虑计算斐波那契数列

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

假设a和b在Java中是biginteger或者其他可以处理任意大数字的东西。大多数人会毫不犹豫地说这是一个O(n)算法。理由是，在for循环中有n次迭代，而O(1)工作在循环的一侧。

但是斐波那契数列很大，第n个斐波那契数列是n的指数级，所以仅仅是存储它就需要n个字节。对大整数执行加法将花费O(n)个工作量。所以在这个过程中所做的总功是

一加二加三……+ n = n(n-1)/2 = O(n)

所以这个算法在二次时间内运行!

基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。

很少(除非你正在编写一个具有广泛基库的平台(例如，.NET BCL或c++的STL)，你会遇到比查看循环(for语句，while, goto等…)更困难的事情。

小提示:大O符号是用来表示渐近复杂度的(也就是说，当问题的大小增长到无穷大时)，它隐藏了一个常数。

这意味着在O(n)和O(n2)的算法之间，最快的并不总是第一个算法(尽管总是存在一个值n，这样对于大小为>n的问题，第一个算法是最快的)。

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

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

有不同的时间复杂度:

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

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

正如你所说，过早的优化是万恶之源，(如果可能的话)在优化代码时真的应该总是使用分析。它甚至可以帮助您确定算法的复杂性。

除了使用主方法(或其专门化之一)之外，我还通过实验测试了我的算法。这不能证明达到了任何特定的复杂度等级，但它可以保证数学分析是适当的。为了保证这一点，我将代码覆盖工具与我的实验结合起来使用，以确保我使用了所有的案例。

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

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

以下是一些最常见的案例，摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

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

O(logn) -用二分搜索在排序数组中查找一个项

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

O(n2) -用一个简单的算法乘以两个n位数字;添加两个n×n矩阵;冒泡排序或插入排序

O(n3) -用简单的算法乘以两个n×n矩阵

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

O(n!) -通过暴力搜索解决旅行推销员问题

O(nn) -通常用来代替O(n!)来推导更简单的渐近复杂度公式

我认为，一般来说用处不大，但为了完整起见，还有一个Big Omega Ω，它定义了算法复杂度的下界，还有一个Big Theta Θ，它同时定义了上界和下界。

不要忘记考虑空间的复杂性，如果内存资源有限，这也是一个值得关注的问题。例如，你可能听到有人想要一个常数空间算法，这基本上是说算法所占用的空间量不依赖于代码中的任何因素。

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

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

如果您希望根据经验而不是通过分析代码来估计代码的顺序，您可以插入一系列不断增加的n值，并为代码计时。在对数刻度上绘制你的时间。如果代码是O(x^n)，值应该落在斜率为n的直线上。

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

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

你的基本工具是决策点及其熵的概念。一个决策点的熵是它会给你的平均信息。例如，如果一个程序包含一个有两个分支的决策点，它的熵是每个分支的概率乘以该分支的逆概率的log2的和。这就是你从执行决策中学到的东西。

例如，一个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 =约0.01 bit。你学得太少了!第二个决定也好不到哪里去。这就是为什么线性搜索这么慢。事实上，你需要学习的比特数是指数级的。

假设你在做索引。假设表被预先排序到许多箱子中，并且您使用键中的所有位中的一些位直接索引到表项。如果有1024个箱子，熵为1/1024 * log(1024) + 1/1024 * log(1024) +…对于所有1024个可能的结果。这是1/1024 * 10乘以1024个结果，或者对一个索引操作来说是10比特的熵。这就是为什么索引搜索是快速的。

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

基于二元决策的排序结果都是等概率的都需要O(N log N)步。基于索引搜索的O(N)排序算法是可行的。

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

经常被忽视的是算法的预期行为。它不会改变你的算法的大o，但它确实与“过早优化.. ..”的声明有关

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

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

为了真正确定它，你需要能够描述你的“输入空间”的概率分布(如果你需要对一个列表排序，这个列表已经被排序的频率是多少?有多少次是完全相反的?多长时间进行一次排序?)这并不总是可行的，但有时你知道。

至于“如何计算”大O，这是计算复杂性理论的一部分。对于一些(许多)特殊的情况，您可能会使用一些简单的启发式方法(例如为嵌套循环乘以循环计数)，特别是当您想要的只是任何上限估计时，并且您不介意它是否过于悲观——我猜这可能就是您的问题的内容。

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

如果你的成本是一个多项式，只保留最高次项，而不保留它的乘数。例如:

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

注意，这对无穷级数不成立。对于一般情况，没有单一的方法，但对于一些常见情况，适用以下不等式:

O（log N） < O（N） < O（N log N） < O（N2） < O（Nk） < O（en） < O（n！）

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

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

我将尽最大努力在这里简单地解释它，但请注意，这个主题需要我的学生几个月才能最终掌握。你可以在《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接受数据。长度值。现在我们需要函数f()的实际定义。这是从源代码中完成的，其中每个感兴趣的行编号从1到4。

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

我们将添加函数的步数，局部变量声明和return语句都不依赖于数据数组的大小。

这意味着第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，我们需要函数的渐近分析。大致是这样做的:

去掉所有常数C。 由f()得到多项式的标准形式。 对多项式的项进行除法，并按增长率对它们排序。 保留N趋于无穷时变大的那一个。

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，第二个用于执行: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执行复杂度。

现在可以使用一些恒等规则来简化求和:

求和(w从1到N)(C) = N * C 求和(w from 1 to N)(A (+/-) B) =求和(w from 1 to N)(A)(+/-)求和(w from 1 to N)(B) 求和(w从1到N)(w * C) = C *求和(w从1到N)(w) (C是一个常数，与w无关) 求和(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²+ 2n + 1我们有两个规则:

如果我们有一个项的和，增长率最大的项被保留，其他项被省略。 如果我们有几个因数的乘积，常数因数就省略了。

如果我们化简f(x)，其中f(x)是所做操作数量的公式，(上文解释的4n²+ 2n + 1)，我们得到大O值[在这种情况下是O(n²)]。但这必须考虑到程序中的拉格朗日插值，这可能很难实现。如果真正的大O值是O(2^n)我们可能有O(x^n)这样的东西，那么这个算法可能是不可编程的。但如果有人证明我错了，给我代码. . . .

让我们从头说起。

首先，接受这样一个原则:对数据的某些简单操作可以在O(1)时间内完成，即在与输入大小无关的时间内完成。C语言中的这些基本操作由

算术运算(例如+或%)。 逻辑操作(如&&)。 比较操作(例如，<=)。 结构访问操作(例如A[i]这样的数组索引，或指针后跟 使用->操作符降低)。 简单的赋值，例如将值复制到变量中。 调用库函数(例如，scanf, printf)。

要证明这一原理，需要对典型计算机的机器指令(基本步骤)进行详细研究。所描述的每一个操作都可以用少量的机器指令来完成;通常只需要一个或两个指令。 因此，C语言中的几种语句可以在O(1)时间内执行，也就是说，在与输入无关的某个常数时间内执行。这些简单的包括

表达式中不涉及函数调用的赋值语句。 读语句。 编写不需要调用函数来计算参数的语句。 跳转语句有break、continue、goto和return表达式 表达式不包含函数调用。

在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次， 由于0是i的初始值，n−1是i达到的最大值(即当i 到达n−1时，循环停止，当I = n−1)时不发生迭代，并添加1 在循环的每一次迭代中。

In the simplest case, where the time spent in the loop body is the same for each iteration, we can multiply the big-oh upper bound for the body by the number of times around the loop. Strictly speaking, we must then add O(1) time to initialize the loop index and O(1) time for the first comparison of the loop index with the limit, because we test one more time than we go around the loop. However, unless it is possible to execute the loop zero times, the time to initialize the loop and test the limit once is a low-order term that can be dropped by the summation rule.

---

现在想想这个例子:

(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 in 每次迭代，得出每次外循环迭代花费O(n)时间。

外部循环的初始化i = 0和条件的(n + 1)st检验 i < n同样需要O(1)次，可以忽略。最后，我们观察到我们走了 绕外循环n圈，每次迭代花费O(n)时间，得到总数 O(n²)运行时间。

---

一个更实际的例子。

好问题!

免责声明:这个答案包含虚假陈述，见下面的评论。

如果您正在使用大O，那么您正在谈论的是最坏的情况(后面将详细介绍它的含义)。此外，在平均情况下有大写的theta，在最佳情况下有大的omega。

你可以在这个网站上找到大O的正式定义:https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n))表示存在正常数c和k，使得当n≥k时0≤f(n)≤cg(n)。对于函数f, c和k的值必须是固定的，且不依赖于n。

---

好的，那么我们所说的"最佳情况"和"最坏情况"是什么意思呢?

这一点可以通过例子得到最清楚的说明。例如，如果我们使用线性搜索在一个排序数组中查找一个数字，那么最坏的情况是我们决定搜索数组的最后一个元素，因为这将花费与数组中有多少项一样多的步骤。最好的情况是当我们搜索第一个元素时，因为我们将在第一次检查之后完成。

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.

抱歉，这是如此糟糕的写作和缺乏太多的技术信息。但希望这能让时间复杂度类更容易理解。一旦你熟悉了这些，你就可以很简单地解析你的程序，寻找像for-loops这样依赖于数组大小的东西，并根据你的数据结构推理什么样的输入会导致简单的情况，什么样的输入会导致最坏的情况。

我想从另一个角度来解释Big-O。

Big-O只是用来比较程序的复杂性，也就是当输入增加时它们的增长速度有多快，而不是花在执行操作上的确切时间。

恕我直言，在大o公式中，你最好不要使用更复杂的方程(你可以坚持使用下图中的方程)。然而，你仍然可以使用其他更精确的公式(如3^n, n^3，…)，但有时会误导!所以还是尽量简单为好。

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

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

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表示输入集中的条目数， f表示每一项所做的操作。

---

Big-Oh符号是算法复杂度的渐近上界。 在编程中:假设的最坏情况所花费的时间， 或假设逻辑的最大重复计数，为输入的大小。

计算

记住(从上面的意思);我们只需要受N(输入大小)影响的最坏情况时间和/或最大重复次数， 然后再看一下(公认答案的)例子:

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

Begin with this search-pattern: Find first line that N caused repeat behavior, Or caused increase of logic executed, But constant or not, ignore anything before that line. Seems line hundred-twenty-three is what we are searching ;-) On first sight, line seems to have 2*n max-looping. But looking again, we see i += 2 (and that half is skipped). So, max repeat is simply n, write it down, like f(n) = O( n but don't close parenthesis yet. Repeat search till method's end, and find next line matching our search-pattern, here that's line 124 Which is tricky, because strange condition, and reverse looping. But after remembering that we just need to consider maximum repeat count (or worst-case time taken). It's as easy as saying "Reverse-Loop j starts with j=n, am I right? yes, n seems to be maximum possible repeat count", so: Add n to previous write down's end, but like "( n " instead of "+ n" (as this is inside previous loop), and close parenthesis only if we find something outside of previous loop.

搜索完成了!为什么?因为第125行(或之后的任何行)与我们的搜索模式不匹配。 现在我们可以关闭任何圆括号(在我们的记录中左开)，结果如下:

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

试着进一步缩短“n(n)”部分，比如:

N (N) = N * N = n2 最后，用Big Oh符号来包装它，就像O(n2)或O(n²)一样，没有格式。