第九章 分析 (Analysis)
分析章节是一个可选章节;它一般出现在设计章节之后,是对设计章节的补充和延展。因研究问题的不同,分析章节的内容也不尽相同。
有的文章在分析章节中着眼于设计本身,进行一些理论的定性分析。而另一些文章的分析章节则将重点放在新方法的应用和扩展上。
本节我们仅给出一些撰写分析章节的思路,以供读者参考。
算法复杂度分析。算法复杂度分析是一种常见的分析内容。算法复杂度分析可分为时间复杂度分析和空间复杂度分析两种。
一般情况下,假设算法输入数据量为n,那么,分析的目的是找出一个与n相关的复杂度函数f(n)。
这个复杂度可能还会分为最优情况下的复杂度,平均复杂度,和最坏情况下的复杂度。
以上内容都是常规分析,我们可以尝试再进一步。如果输入数据满足一定条件,那么,是否能够得到更加有意义的分析结果呢?
例如,假如输入数据遵循均匀分布,那么,是否能得到一个更加精确的算法时间复杂度或者空间复杂度呢?这个分析背后的意义在于,
假如有一种应用场景,其输入数据是均匀分布的,那么,上述的分析结果就可以直接应用到这个场景中了。当然,不同的应用场景,
输入数据的特点是不同的,这需要根据研究问题的特性相应变化。值得指出的是,如果按照这个思路,假设输入数据满足一个具体的概率分布函数/概率密度函数,
那么,概率和随机过程的知识是一个很好的可利用的分析工具。