大多数拥有计算机科学学位的人肯定知道大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)
其他回答
小提示:大O符号是用来表示渐近复杂度的(也就是说，当问题的大小增长到无穷大时)，它隐藏了一个常数。
这意味着在O(n)和O(n2)的算法之间，最快的并不总是第一个算法(尽管总是存在一个值n，这样对于大小为>n的问题，第一个算法是最快的)。
注意，隐藏常数很大程度上取决于实现!
此外，在某些情况下，运行时并不是输入大小为n的确定函数。以快速排序为例:对n个元素的数组进行排序所需的时间不是一个常数，而是取决于数组的初始配置。
有不同的时间复杂度:
最坏的情况(通常是最简单的，但并不总是很有意义) 一般情况下(通常很难弄清楚…) .．.
一个很好的介绍是R. Sedgewick和P. Flajolet的《算法分析导论》。
正如你所说，过早的优化是万恶之源，(如果可能的话)在优化代码时真的应该总是使用分析。它甚至可以帮助您确定算法的复杂性。
大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²。
这仅仅是触及表面，但当你分析更复杂的算法时，涉及证明的复杂数学就会发挥作用。希望这至少能让你熟悉基本知识。
将算法分解成你知道的大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)
虽然知道如何计算出特定问题的大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!)来推导更简单的渐近复杂度公式
