🎇🎇🎇作者:
@小鱼不会骑车
🎆🎆🎆专栏:
《java练级之旅》
🎓🎓🎓个人简介:
一名专科大一在读的小比特,努力学习编程是我唯一的出路😎😎😎
今天小鱼讲到的是关于时间复杂度和空间复杂度的理解。
时间复杂度
前言
我们来举个例子!
假如我们有A,B两台电脑,A电脑的执行速度是1000次/s,B电脑的执行速度是1次/s,假如两台电脑都执行相同的代码,那么是不是我的A电脑会更快的完成任务。
答案是:对的!
但是我们改变一下条件,假设两台电脑需要完成一个查找数组中指定元素的任务,A电脑中的代码每次可以遍历1个元素,B电脑中的代码每次可以遍历100个元素。那么大家认为这两台电脑哪一个会更快的完成任务?
通过这个图表我们就可以看出,当运行到10秒时,我们的B对元素遍历的次数已经和A持平了,再往后面我们的B的遍历次数更是远超A.
于是我们可以通过上图的对比看出,哪怕是电脑的性能很好很优良,但是却还依然跑不过B,这就体现到了代码运行效率的重要性!
时间复杂的讲解
上面举得例子只是为了让大家知道代码运行效率的重要性,下面才是真正的讲解如何计算代码的运行效率!
大家看这段代码!
public static void main(String[] args) {
int n=100;
while ((n)!=0) {
n--;
}
}
大家认为这段代码会运行多久?
可能就会有同学回答说:这个要放计算机上跑跑才知道吧…
那我如果将n改为10000呢?需要运行多久啊?
同学:这个…要不再测试一次?
其实呀,我们并不能精准的测量出程序运行的时间,有的计算机的运行速度会快一些,有的则会慢一些…于是呢,就有人提出了用计算机的语句的执行次数来当作计算机的时间效率,而不是运行的时间。
我们来算算上述的代码执行了多少次
为了方便讨论,这里我们把每一条语句的执行时间都看做是一样的,记为一个时间单元
由于黄色的最后还需要判断一次,所以需要n+1个时间单元 !
那么我们就可以计算出这个程序的语句执行了多少次,我们可以用函数来表达:y=n+n+1+1,化简就是:y=2n+2;函数图像就是
所以,如果要预测程序运行的时间我们可以把运行时间函数求出来。
可是如果光看这个函数还是有些复杂啊!
其实呀,我们平时都会对这些函数进行简化的,使得它既简单又没有失去函数得主要特性。
咦?那怎么简化啊?
如何简化时间复杂度
对于时间复杂度来说,我们比较关心的就是影响最终结果的最高次项。
比如说:T(n)=2n+2, 当n非常大的时候常数2和n的系数2对函数结果的影响就很小了
例如:
T(n)=n+1 忽略常数项 T(n)~n
T(n)=n+n^2 忽略低阶项 T(n)~n^2
T(n)=3n 忽略最高阶的系数 T(n)~n
所谓低阶项就是当n很大时,该项对于这个数的影响很小,比如n相对于n^2来说,n就是低阶项!
对此呢,我们有一个比较的关系,不同项进行比较只保留最高阶项,比较关系如下
化简后的函数可以代表原函数的总体趋势,并且简化后的式子就可以称为这个算法的时间复杂度,记作O(f(n)),其中f(n)是简化后的式子,例如刚才的T(n)=2*n+2,简化后为T(n)~ f(n) ~ n,所以我们也可以记作O(n).
更准确地说O代表了运行时间函数的一个渐进上界,即T(n)在数量级上小于等于f(n)
那我们如何计算时间复杂度呢?
时间复杂度的计算
经过了前面的两个小部分的讲解,我们也可以总结出:计算算法复杂度大O的方法
一.得出运行时间的函数
二.对该函数进行简化
1.用常数1取代运行时间中所有加法常数
2.修改后的函数只保留最高阶项
3.如果最高阶项存在,并且不是1,则忽略这个最高项数的系数
举个例子,看下面代码:
我们可以看出,T(n)=5,我们可以对这个函数进行简化,将他的常数项用1来取代,又因为该函数没有最高阶项,所以他的时间复杂度就是O(1)。
O(1)也被称为常数阶
当然啦,如果我们一个一个去数语句再去计算函数是很麻烦的,有没有简便一些的方法吗?
其实是可以偷偷懒的,一般来说程序最内层执行次数最多的语句就决定了整个函数的趋势。
我们只需要找到最内层语句执行次数的规律就行!所以我们就可以清楚的得出上面的时间复杂度是O(n).
并且呢,我们也可以根据这个方法得出下面这个代码的时间复杂度O(n^2)
.
如果还有人不太理解这个O(n^2)这个时间复杂度的意思,我给大家用数学的角度来算一下!
所以我们可以理解为上述的代码的时间复杂度为O(n^2)
下面再来介绍最后一个比较牛 * 的时间复杂度O(log2N),读作log以2为底N的对数。
怎么个牛 * 法呢?二分查找大家都知道吧,在一个有序数组里查找指定的元素,如果我们用从前往后遍历的方式来查找,我们用这个世界的人口举例
我们简单认为是76亿人,所以我们假设这个数组是76亿个元素,如果我们想从这76亿个元素中查找到一个指定的元素,那么最坏的情况就是查找76亿次,多么庞大的次数啊。
但是!假设这是一个有序数组,该数组有76亿个元素,大家猜猜我们需要查找多少次?
答案是我们只需要查找33次,就可以找到这个要被查找的元素,牛不牛!
我们再来看看O(logN)的函数图像
上下图对比,它随着自变量的增大,因变量增长的很慢很慢!
int a=1;
while (a<=n) {
a*=2;
}
这段代码的复杂度就是对数级别的,O(logn)。
怎么计算它的时间复杂度呢?
复杂度的内容好多,会一直伴随着我们学习数据结构与算法,所以我们现在只需呀简单理解复杂的的含义就行!文章来源:https://www.toymoban.com/news/detail-817502.html
文章来源地址https://www.toymoban.com/news/detail-817502.html
到了这里,关于如果各位同学还对时间复杂度有疑问?看这一篇就可以啦!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!