实战测试复杂度分析这种方法叫做“事后统计法”，这种方法有几个弊端：
测试结果非常依赖测试环境
测试结果受数据规模的影响很大（如数据规模小，结果无法真实反应出算法的性能问题）
所以这种方法并不是太好，更好的方法是我们可以直接超越硬件要求来分析时间复杂度。
大O复杂度表示法：
1、大O时间复杂度的由来：
算法的实行效率，粗略的讲就是算法代码的执行时间。从CPU的角度讲，每行代码都执行着类似的操作：读数据-运算-写数据。粗略计算的时候，我们可以假设每行代码的执行时间都是一样的，记为t，一段代码的总执行时间记为T(n)
1 int cal(int n) {
2 int sum = 0; //执行1次
3 int i = 1; //执行1次
4 for (; i <= n; ++i) { //执行n次
5 sum = sum + i; //执行n次
6 }
7 return sum;
8 }
对于上述代码段，我们可以计算出T(n)=(2n+2)t，即代码的执行时间T(n)和每行代码的执行次数成正比。
再来分析一段代码
1 int cal(int n) {
2 int sum = 0; //执行1次
3 int i = 1; //执行1次
4 int j = 1; //执行1次
5 for (; i <= n; ++i) { //执行n次
6 j = 1; //执行n次
7 for (; j <= n; ++j) { //执行n*n次
8 sum = sum + i * j; //执行n*n次
9 }
10 }
11 }
对于上述代码段，T(n)=(2n²+2n+3)t
2、大O时间复杂度的表示法：
基于一段代码的执行时间和每行代码的执行次数成正比，我们记为 T(n)=O(f(n))，f(n)表示每行代码的执行次数总和。
所以对于第一段代码有T(n)=O(2n+2)，第二段代码有T(n)=O(2n²+2n+3)。这就是所谓的大O表示法，大O的官称是渐进时间复杂度（asymptotic time complexity），他实际上并不具体表示代码真正的执行实行，而是表示代码执行时间随数据规模增长的变化趋势。所以式子中的低阶项、常数项、及系数并不能左右这种变化趋势，是可以直接忽略的，我们可以只记录一个最大量级，比如，第一段记作T(n)=O(n)，第二段记作T(n)=O(n²)。
3、大O时间复杂度分析
基本策略：由内向外，从最深层开始分析；遇到函数要进入函数里面进行分析。
3.1，只关注循环执行次数最多的一段代码
1 int cal(int n) {
2 int sum = 0; //执行1次
3 int i = 1; //执行1次
4 for (; i <= n; ++i) { //执行n次
5 sum = sum + i; //执行n次
6 }
7 return sum;
8 }
解释：第 2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。前面我们也讲过，这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。
再举个例子
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) { //常数量级--忽略
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) { //执行n次
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) { //执行n次
j = 1;
for (; j <= n; ++j) { //执行n*n次
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
解释：从前文可分析出 sum_1、sum_2、sum_3这三部分的时间复杂度，分别是常数量 、O(n) 、O(n²)，直观可得计算sum_3的循环执行次数最多，所以本例的时间复杂度是O(n²)。
另外需要注意的一点是对于一段代码中有多个数据规模时，由于我们不能直观的看出其规模大小次序，所以要视情况而定，比如：
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。
常见的时间复杂度量级：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n^k) <O(2ⁿ)<O(n!)
上述时间复杂度可被粗略的分为多项式量级和非多项式量级，其中，非多项式量级只有两个：O(2ⁿ) 和O(n!)。
注：非多项式量级的算法问题被称作NP（Non-Deterministic Polynomial，非确定多项式）问题
（当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。）
对于我们常见的多项式量级复杂度，我们主要分析O(logn)和O(nlogn)
1 i=1;
2 while (i <= n) {
3 i = i * 2;
4 }
基于前文，我们很容易看出第三行代码执行次数最多，只要计算出该行的执行次数，便可得该段代码的时间复杂度。
从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列：
2 2² 2³ .... 2^k 2^x =n
上句中的x便是该循环的执行次数，通过2^x =n求得
x=log_2 n
所以这段代码的时间复杂度为
O(log_2 n)
对上述代码稍作改动：
1 i=1;
2 while (i <= n) {
3 i = i * 3;
4 }
得时间复杂度为
O（log_3 n）
又因为对数的数学运算法则，我们知道
log_3 n=log_2 n*log_3 2
所以不管对数的底数是几，我们都统一记其时间复杂度为O(logn)
3.2，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
1int cal(int n) {
2 int ret = 0;
3 int i = 1;
4 for (; i < n; ++i) {
5 ret = ret + f(i); //执行n*T(f(i))次
6 }
7 }
8
9 int f(int n) {
10 int sum = 0;
11 int i = 1;
12 for (; i < n; ++i) {
13 sum = sum + i; //执行n次
14 }
15 return sum;
16 }
若函数f(i)只是普通操作，则该段时间复杂度为O(n)，因为涉及到函数的嵌套，所以该段时间复杂度为嵌套内外代码的乘积，即O(n²)
