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

作为一个非常简单的例子，假设你想要对. 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，这是计算复杂性理论的一部分。对于一些(许多)特殊的情况，您可能会使用一些简单的启发式方法(例如为嵌套循环乘以循环计数)，特别是当您想要的只是任何上限估计时，并且您不介意它是否过于悲观——我猜这可能就是您的问题的内容。

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

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

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

假设我们有这样一个函数(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运算符组合。这是我知道的唯一办法。

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

对于代码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)这样的东西，那么这个算法可能是不可编程的。但如果有人证明我错了，给我代码. . . .