算法分析

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

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

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

n_{}0

使得当N

\geq

n_{}0

时，T(N)

\leqslant

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

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

n_{}0

使得当N

\geq

n_{}0

时，T(N)

\leqslant

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

\Omega

(g(N))。

定义：T(N)=

\Theta

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

\Omega

(h(N)).

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

\neq

\Theta

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

例如，

N^{3}

增长率比

N^{2}

快，则可以说

N^{2}

=O(

N^{3}

）,或者

N^{3}

=

\Omega

（

N^{2}

）.

法则1：

如果

T_{1}=O(f(N))且T_{2}(N)=O(g(N))

且

T_{2}(N)=O(g(N))

那么

（a）

T_{1}(N)+T_{2}=max(O(f(N)),O(g(N))

,

（b）

T_{1}(N)*T_{2}=O(f(N)*g(N))

法则2：

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

T(N)=\Theta (N^{k})

法则3：

对任意常数k,

log^{k}N=O(N)

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

一、运行时间计算

法则1-for循环

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

法则2-嵌套for循环

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

法则3-顺序语句

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

法则4-IF/ELSE

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