至于“如何计算”大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);

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

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

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

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

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

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

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

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

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

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

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

有不同的时间复杂度:

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

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

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