算法与数据结构(2):算法复杂度


复杂

9月5日,星期三,公元2018年。

简书作者程序员联盟:目前正在更新这个系列的教程,我是学习记录者,并非原创,此后算法与数据结构系列都是记录笔记,不再进一步说明。

这片是关于引出算法复杂度,用了小鸭子的故事。

小鸭子

小鸭子

故事是这样的:

有个农夫,每年带着小鸭子们去旅行,目的是为了让小鸭子们都得到放松清净的机会。旅行就是将他们放到池塘里,而且每个池塘要保证一样多的鸭子,才能够同样的清净,不会有不公平的情况出现。因此,农夫采取的方法是:将小鸭子一只一只的带到池塘边,让他们自己选择要去的池塘,最后在池塘和卡车之见跑了NxN个来回。而第二年,农夫发现不太好,于是就重新换了方法,依次带出N只鸭子,将其放在一个池塘,如此下去,直到每个池塘也是同样多的鸭子,这样只需要N个来回。这样一算,发现第二种方法能够更节省时间更轻松,而且还达到了同样的效果,新的方法胜利。

农夫的放鸭子的方法,就可以看成一种算法,用来对放置鸭子进行了精确的描述。很显然第二种算法更好,时间节省,力气节省,还能达到同样的结果。在计算机术语中,人们用复杂度(complexity)这个词来量化算法的性能。

坚持原创技术分享,您的支持将鼓励我继续创作!