大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇，你是如何计算或近似你的算法的复杂性的?
当前回答
如果你的成本是一个多项式，只保留最高次项，而不保留它的乘数。例如:
(O (n / 2) + 1) * (n / 2)) = O (n2/4 = O (n / 2) + n2/4) = O (n2)
注意，这对无穷级数不成立。对于一般情况，没有单一的方法，但对于一些常见情况，适用以下不等式:
O（log N） < O（N） < O（N log N） < O（N2） < O（Nk） < O（en） < 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!)来推导更简单的渐近复杂度公式
熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于，当您调用一个库函数时，可能会多次调用—您常常不确定是否在不必要的时候调用了函数，或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量，无论是大O还是其他度量，都可以在文档或智能感知中得到。
我认为，一般来说用处不大，但为了完整起见，还有一个Big Omega Ω，它定义了算法复杂度的下界，还有一个Big Theta Θ，它同时定义了上界和下界。
对于代码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运算符组合。这是我知道的唯一办法。
欲了解更多信息，请查看有关该主题的维基百科页面。
