全部学习汇总: https://github.com/GreyZhang/g_SICP
不知道如何翻译原来的章节标题,但是从内容来看应该是要引入算法复杂度增长的概念。在以往看到的书籍中,或许大家直接称之为算法复杂度的就是这个。
而这里的描述其实更加精准一些,总结来说是能够表征这个算法的资源占用情况与输入的关系的一种表述方式。
在描述算法的复杂度的时候,有一个给定的大小n不一定会是步数。比如,求解近似平方根的时候,这个n其实也可以定义为是平方根精度的位数。如果是计算矩阵的乘法,那么这个n可以是不同的矩阵的维度。针对不同的处理对象,可以从不同的角度进行分析。
接下来,给出来了这个算法复杂度增长的一个概念性的表述。由此来看,其实并不是所有的算法都能够有一个可以总结出来的一个复杂度表述的描述。
算法效率或者复杂度的评估不仅仅是一个方面的评估,大致来说其实可以分为两部分。第一部分是执行步骤次数或者干脆称之为执行次数的评估;另一部分则是算法对于资源消耗的一个评估。
有些算法的描述其实能够在复杂度上做出很好的估计,但是有些时候估计会有一定的偏差。但是即便如此,类似的估计依然能够让我们对算法随着输入复杂度的发展而进行的变化做出一定的推演预测。在接下来的介绍内容里面,还会介绍两种复杂度满足对数规律的算法。对此,还需要认真分析一下。之前这部分薄弱的知识是时候补充一下了。