算法分析

算法是为求解一个问题需要遵循的、被清楚的指定的简单指令集合。

估计算法资源消耗所需的分析一般来说是一个理论问题，因此需要一套正式的系统架构。

定义：如果存在正常数c和

使得当N

时，T(N)

cf(N),则记为T(N)=O(f(N))。

定义：如果存在正常数c和

使得当N

时，T(N)

cg(N),则记为T(N)=

(g(N))。

定义：T(N)=

(h(N)),当且仅当T(N)=O(h(N))且T(N)=

(h(N)).

定义：如果T(N)=O(h(N)),当且仅当T(N)

(h(N)),则T(N)=o(p(N)).

例如，

增长率比

快，则可以说

=O(

）,或者

=

（

）.

法则1：

如果

且

那么

（a）

,

（b）

法则2：

如果T(N)是一个k次多项式，则

法则3：

对任意常数k,

首先将常数或低阶项放进大O是非常坏的习惯。

一、运行时间计算

法则1-for循环

一次for循环的运行时间至多该for循环内语句（包括测试）的运行时间迭代的次数

法则2-嵌套for循环

从里向外分析这些for循环。在一组嵌套for循环内部的一条语句，总的运行时间为该语句的运行时间乘以该组所有的for循环的大小乘积。

法则3-顺序语句

将各个语句的运行时间求和即可

法则4-IF/ELSE

一个if/else语句的运行时间从不超过判断再加上S1和S2中运行时间长者的总运行时间。