这篇文章主要介绍数据结构之一组图让你搞懂时间复杂度的案例,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
<强> 
<强>时间复杂度的意义
究竟什么是时间复杂度呢?让我们来想象一个场景:某一天,小灰和大黄同时加入了一个公司……
一天过后,小灰和大黄各自交付了代码,两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒,内存占用5 mb。小灰的代码运行一次要花100秒内存占用500 mb。于是……
由此可见,衡量代码的好坏,包括两个非常重要的指标:
1。运行时间,
2。占用空间。
<强> 
<>强基本操作执行次数
关于代码的基本操作执行次数,我们用四个生活中的场景,来做一下比喻:
<>强场景1:给小灰一条长10寸的面包,小灰每3天吃掉1寸,那么吃掉整个面包需要几天?
答案自然是3 X 10=30天。
如果面包的长度是N寸呢?
此时吃掉整个面包,需要3 X N=3 N天。
如果用一个函数来表达这个相对时间,可以记作T (N)=3 N。
<>强场景2:给小灰一条长16寸的面包,小灰每5天吃掉面包剩余长度的一半,第一次吃掉8寸,第二次吃掉4寸,第三次吃掉2寸……那么小灰把面包吃得只剩下1寸,需要多少天呢?
这个问题翻译一下,就是数字16不断地除以2,除几次以后的结果等于1 ?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log16。
因此,把面包吃得只剩下1寸,需要5 X log16=5 * 4=20天。
如果面包的长度是N寸呢?
需要5 X logn=5 logn天,记作T (N)=5 logn。
<>强场景3:给小灰一条长10寸的面包和一个鸡腿,小灰每2天吃掉一个鸡腿,那么小灰吃掉整个鸡腿需要多少天呢?
答案自然是2天,因为只说是吃掉鸡腿,和10寸的面包没有关系。
如果面包的长度是N寸呢?
无论面包有多长,吃掉鸡腿的时间仍然是2天,记作T (N)=2 .
<>强场景4:给小灰一条长10寸的面包,小灰吃掉第一个一寸需要1天时间,吃掉第二个一寸需要2天时间,吃掉第三个一寸需要3天时间.....每多吃一寸,所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢?
答案是累从1加到10的总和,也就是55天。
