复杂度理论初步
在算法竞赛中,我们不但要保证输出结果的正确性,还要在规定的时间内完成计算,才能够拿到该测试点的分数。一个问题可能有很多种算法来解决,但耗时有显著差异。冒泡排序一个长度为 $100000$ 的数组,耗时几分钟;快速排序耗时不到一秒钟。而衡量时间的多少,我们不一定非要逐个跑程序。在设计代码之前,我们往往可以估测耗时,这就需要用到复杂度理论。
在算法竞赛中,我们不但要保证输出结果的正确性,还要在规定的时间内完成计算,才能够拿到该测试点的分数。一个问题可能有很多种算法来解决,但耗时有显著差异。冒泡排序一个长度为 $100000$ 的数组,耗时几分钟;快速排序耗时不到一秒钟。而衡量时间的多少,我们不一定非要逐个跑程序。在设计代码之前,我们往往可以估测耗时,这就需要用到复杂度理论。
部分转载自Python 30分钟入门指南 by Luogu Dev Team,如有侵权,请联系 slzwzjn1212@outlook.com 以删除。
这是我在知乎上发表的第一篇回答。