算法分析

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

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

定义：如果存在正常数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中运行时间长者的总运行时间。

文章来源: xintiaobao.blog.csdn.net，作者：心跳包，版权归原作者所有，如需转载，请联系作者。

原文链接：xintiaobao.blog.csdn.net/article/details/89456477