算法执行效率的评估
- 经验法：对各种算法编程，用不同实例进行实验；
- 理论法：以数学化的方式确定算法所需要资源数与实例大小之间函数关系。
经验法的问题
- 依赖于计算机
- 依赖于语言/编程技能
- 需要一定的编程/调试时间
- 只能评估部分实例的效率
理论法的优点
- 不依赖于计算机
- 不依赖于语言/编程技能
- 节省了无谓编程时间
- 可研究任何在实例上算法效率
算法好坏的衡量
最初，用所需计算时间来衡量算法的好坏。但不同的机器相互之间无法比较，故需要用独立于具体计算机的客观衡量标准：
问题的规模
输入规模通常用 $n$ 来表示，也可有两个以上的参数，如图中的顶点数和边数。
基本运算
基本运算是解决给定问题时占支配地位的运算。通常情况下，讨论一个算法优劣时，我们只讨论基本运算的执行次数。因为它是占支配地位的，而其它的运算可以忽略不计。
基本运算是算法中最为基本的运算，在伪代码中很容易识别，而且与编程语言无关。假设在每个基本运算都在RAM模型中花费一定的时间，无需精确衡量执行多少时间。
算法的计算量函数
$$ C = T(N, I, A) $$式中，$N$ 表示问题的规模，$I$ 表示输入，$A$ 表示算法本身。
变量 $A$ 可以隐去，通常研究算法在一台抽象计算机上运行所需时间。
其实变量 $I$ 也可以隐去，因为不必研究每种合法输入的计算量，只需要考虑算法的最好情况、最坏情况和平均情况。
那么最终算法的计算量函数就可以简化为：
$$ C = T(N) $$算法的时间复杂度
用输入规模的某个函数来表示算法的基本运算量，称为算法的时间复杂度，即：
$$ C = T(N) $$复杂性渐进形态
当比较两个算法的渐近复杂性的阶不同时，只要确定各自的阶，即可判定哪个算法效率高。
- 渐近上界记号 $O$
- 渐进下界记号 $\Omega$
- 紧渐近界记号 $\Theta$
- 非紧上界记号 $o$
- 非紧下界记号 $\omega$
和的估计与界限
结合数学上的数列求和方法以及求积分的方法求解。