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

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

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

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

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

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

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

首先，公认的答案是试图解释漂亮的花哨的东西， 但我认为，故意让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²)一样，没有格式。

我将尽最大努力在这里简单地解释它，但请注意，这个主题需要我的学生几个月才能最终掌握。你可以在《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²)