从0开始学算法1:一套图 搞懂“时间复杂度”
写在前面:
这篇文章是在公众号: 趣谈编程 中发布的,作者是涛声依旧。是我到目前为止所看到的关于时间复杂度介绍的最好的文章,简介 清晰 明了。
所以拿来po出来 仅供学习交流,如侵则删。
正文:
另外,我这里有个问题,现在计算机硬件越来越强大了,为什么还这么重视时间复杂度呢?
我们来举过一个栗子:
算法A的相对时间规模是T(n)= 100n,时间复杂度是O(n)
算法B的相对时间规模是T(n)= 5n2,时间复杂度是O(n2)
算法A运行在小邦家里的老旧电脑上,算法B运行在某台超级计算机上,运行速度是老旧电脑的100倍。
那么,随着输入规模 n 的增长,两种算法谁运行更快呢?
从表格中可以看出,当n的值很小的时候,算法A的运行用时要远大于算法B;当n的值达到1000左右,算法A和算法B的运行时间已经接近;当n的值越来越大,达到十万、百万时,算法A的优势开始显现,算法B则越来越慢,差距越来越明显。
这就是不同时间复杂度带来的差距。
要想学好算法,就必须理解好时间复杂度这个重要的基石。