分析一个算法之前，需要建立一个实现技术的模型，包括描述所用资源及其代价的模型
RAM模型：单处理器，随机存取RAM
指令一条接一条地执行，没有并发操作（单处理器）
包含真实计算机中的常见指令：算术，数据移动，控制
每条指令所需时间为常量
数据类型为整型和浮点型
灰色领域：真实计算机包含的其他指令，不是常量时间的那种。没有对存储器层次进行建模。
算法运行时间
运行时间取决于输入的内容
相同规模\(n\),不同的序列有不同的运行时间，比如逆序序列或者顺序序列
运行时间取决于数据的规模
\(n\)越大，时间自然越多
一般来说，算法所需时间与输入规模同步增长，因此一个程序的运行时间是其输入的函数
通常我们关心运行时间的上限(最坏情况)
注：我们分析时间时要使用机器独立的时间单位，即不考虑机器不同带来的影响。
插入排序时间分析假设每行每次执行的时间为常量\(c_i\)
for j: 2 to length[A]: do key = A[j] i = j-1 while i>0 and A[i]>key do A[i+1] = A[i] i = i-1 A[i+1] = key
\(cost:c_1;times:n\) (包含跳出循环的那次)
注：for循环是刚刚进入循环时就要判断一次条件，然后再执行j--，再判断条件，直到判断条件不满足，不进入循环。假设循环\(n\)个元素，实际执行\(n+1\) 次比较
\(cost:c_2;times:n-1\)
\(cost:c_3;times:n-1\)
\(cost:c_4;times:\sum\limits_{j=2}^nt_j, t_j\) 为一次for循环中while循环的判断次数
\(cost:c_5;times:\sum\limits_{j=2}^n(t_j-1),\)
\(cost:c_6;times:\sum\limits_{j=2}^n(t_j-1)\)
\(cost:c_7;times:n-1\)
\(t_j\) 取决于与序列排序情况有关，如果已经排好序了，\(A[j-1]\)总是小于key了，所以每次for循环只算判断了一次while，总共\(n-1\)次，如果是逆序，前一个总比后一个大，满足while条件，每次for循环中while判断次数为\(t_j=j-1+1=j\) ，总共\(\sum\limits_{j=2}^n{t_j}\) 次。
总的运行时间：
\(T(n)=c_1n+c_2(n-1)+c_3(n-1)+c_4\sum\limits_{j=2}^n{t_j}+c_5\sum\limits_{j=2}^n(t_j-1)+c_6\sum\limits_{j=2}^n(t_j-1)+c_7(n-1)\)
渐进分析如果一个算法的最坏情况运行时间要比另一个算法的低，我们就常常认为它的效率更高。那么如何比较两个算法的运行时间呢？
渐进表示：忽略每条语句的真实代价，而用常量\(c_i\) 表示，只考虑公式中的最高次项(低阶项相对来说不太重要)，忽略最高次项的常数系数（对于增长率而言，系数是次要的）
在输入的规模较小时，由于常数项和低次项的影响，这种看法有时可能是不对的。对规模足够大的输入来说，这种看法总是对的。
虽然有时候能够精确确定一个算法的运行时间，但通常没有必要。（在RAM模型下，可以精确计算T(n)）
渐近分析更有意义（对不是很小的输入规模而言，从渐进意义上说更有效的算法就是最佳的选择）
渐进符号\(\Theta(g(n))=\{f(n):存在正常数c_1,c_2,n_0,对所有的n\ge{n_0},有0\le{c_1g(n)\le{f(n)}\le{c_2g(n)}}\}\)
\(\Theta(g(n))\) 是一个集合，记号\(f(n)=\Theta(g(n))\) 是指\(f(n)\) 是这个集合中的一个元素，不是指相等
具体来说：当\(n\)大于某个数时，一个与\(n\)有关的函数\(f(n)\)，不管\(n\)如何增长，其大小总是被限制到\(c_1g(n)\)和 \(c_2g(n)\)之间。
在时间复杂度分析中，\(f(n)\)即我们所要求的\(T(n)\)，当我们不需要精确地求出\(T(n)\)时，我们只需要大致知道它随\(n\)增长时，其值的上下界如何，即这个算法的运行时间肯定不会超过某个时间，不会低于某个时间。
**比如：\(T(n)=\Theta(n^2)\) 表示该算法的运行时间不会超过\(c_1n^2\) ，不会低于\(c_2n^2\) **
\(\Theta(n^2)\) 是所有满足该性质的算法的\(T(n)\) 的集合
\(O(g(n))=\{f(n):存在正常数c,n_0,对所有的n\ge{n_0},有0\le{f(n)}\le{cg(n)}\}\)
描述了算法运行的上界，不会超过常数倍的\(g(n)\) ，即最坏情况
比如 \(T(n)=O(n^2)\) 表示该算法运行时间不会超过\(cn^2\)
\(\Omega(g(n))=\{f(n):存在正常数c,n_0,对所有的n\ge{n_0},有0\le{cg(n)}\le{f(n)}\}\)
描述算法运行的下界，表示不低于常数倍\(cg(n)\)
一个渐进正函数中的低阶项和最高阶项的系数在决定渐进确界(上界、下界)时可以被忽略