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

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

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

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

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

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

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

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

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

作为一个非常简单的例子，假设你想要对. 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!)来推导更简单的渐近复杂度公式

大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²。

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