如果代码的执行最多总次数可以被表示为一个多项式。 那么时间复杂度就是 保留最高次方、且去掉常数。 之后的结果。 所以，求一段代码的时间复杂度，就是 得到关于次数 t 的多项式，再去掉常数和保留最高次方即可。
此类问题的又可分为两种类型
第一段代码是三层循环嵌套，第二层代码是一层循环。 可以轻易的看出, 第一段代码最内层的语句最多执行 2 n 2 2n^2 2n2 次. 第二段代码最内层最多执行 n 次 所以此段代码的 最多情况下 的总执行次数为 2 n 2 + n 2n^2+n 2n2+n 次, 若记执行次数为, 则 t < = 2 n 2 + n t <= 2n^2+n t<=2n2+n 根据 “留高次，去常数” 的原则, 0 < t < = n 2 0 < t <= n^2 0<t<=n2. 用 “大 O 表示法” 记为 O ( 2 n 2 + n ) O(2n^2 + n) O(2n2+n) 但是当 n → ∞ n\to\infty n→∞ 时， 后面的低次项 n 与常系数 2 就显得微不足道了。所以为了更简洁的描述与比较快慢，可记为 O ( n 2 ) O(n^2) O(n2)
还是刚刚的那段代码,只不过做了些许的改动。就足以让很多同学迷惑
for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) for(int k = 0; k < 2; ++k) if(A[i][j] > 999) A[i][j] = 100; for(int i = 0; i < n; ++i) cout << "999" << endl;可以看出，此程序执行次数最多可能的语句还是 第一层循环的最内层语句
A[i][j] = 100;这样的语句我们称为 主体语句 所以根据 留最高, 去常数。原则，我们只关心主体语句的执行过程，而不用去管第二个循环。此时代码简化为:
for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) for(int k = 0; k < 2; ++k) if(A[i][j] > 999) A[i][j] = 100;又，第三个循环的作用不过是给执行次数 t 的多项式添上系数 2 而已，所以也可以去掉。
for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) if(A[i][j] > 999) A[i][j] = 100;为什么不去掉 判断语句 呢？？因为我们期望得到主体语句的最高执行次数，所以期待每次 判断语句 都会执行。所以在判断复杂度的时候,所以此时可以忽略判断语句。 即:
for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) A[i][j] = 100;此时有两种方法解决这个问题：
第一个循环从 0到n-1 共会执行 n 次 而对于第二个循环对的执行次数取决于第一个循环。
但在最多情况下， 也就是 i = n 时， 第二个循环也会执行到 j = n. 此时两个循从 1 到 n 都执行了 n 次. 所以复杂度依然为 n ⋅ n = O ( n 2 ) n \cdot n = O(n^2) n⋅n=O(n2)
众所周知，当 i = n 时，j所在的循环会执行n次，其中每一次都会使主体语句执行 1, 2 … n 次。 次数如上表所示,所以总执行次数为 留最高, 去常数。后，为 O ( n 2 ) O(n^2) O(n2)
T ( n ) = { 1 , n = 1 , 2 T ( n / 2 ) + n , n > 1. T(n)=\left\{ \begin{aligned} & 1 & , & n=1, \\ 2T(n/2)+n & , & n>1. \end{aligned} \right. T(n)={2T(n/2)+n1,,n>1.n=1, 此类问题分四步走:
写 T(n) 的迭代式(一直文本替换迭代下去)。对每次迭代标号，从1到m。利用 m 与递归截至条件的关系式 解出 m, 代回迭代式。留最高，去常数。例题如下：
我们可以观察到：主体语句执行多少次 取决于 绿色框的值 是否符合循环的判定条件。
此时，我们是无法得知主体语句的循环次数 t 到底是多少的。 这是由于主体语句的循环与否，是取决于循环条件的。 如果满足判定条件，则主体语句循环，循环次数增加。 此类题的解题步骤一般分为 4 步：
列出 主体语句的执行次数 与 绿色框值 的表格 以第一个为例：
建立 F(t) 方程 其中自变量 t 为 主体语句的执行次数，因变量为 绿色框值
将 F(t) 代回循环中的判定条件式，解出 t 变量。 以第一个为例：
n ⩾ ( t + 1 ) 2 ⇒ n ⩾ t 2 + t ⇒ n ⩾ t + t n \geqslant (t+1)^2 \\ \Rightarrow n \geqslant t^2 + t \\ \Rightarrow \sqrt{n} \geqslant t + \sqrt{t} n⩾(t+1)2⇒n⩾t2+t⇒n ⩾t+t 4. 留高次，去常数 t ≤ n 时 间 复 杂 度 为 O ( n ) t \leq \sqrt{n} \\ 时间复杂度为 O(\sqrt{n}) t≤n 时间复杂度为O(n )
