算法分析神器—时间复杂度

算法分析神器—时间复杂度时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度刻画算法的运行时间某日,克叫来了慧子打算给他补习补习一下基础知识,只见克写了一段非

时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度

刻画算法的运行时间

某日,克叫来了慧子打算给他补习补习一下基础知识,只见克写了一段非常简单的代码

算法分析神器—时间复杂度

算法分析神器—时间复杂度

你说一下这段代码会运行多长时间

这个…,得在计算机上跑一下才可以知道吧

算法分析神器—时间复杂度

慧子

算法分析神器—时间复杂度

恩恩,对的,那如果我改变n的大小为10000,你能够预测它的运行时间吗?

这个…,要不再测一次

算法分析神器—时间复杂度

慧子

算法分析神器—时间复杂度

克面无表情

算法分析神器—时间复杂度

我们要善于发现事物的内在规律

克看了一下慧子

这个程序的内在规律是什么呢?

算法分析神器—时间复杂度

慧子

慧子看老师有点生气,开始虚心请教了

算法分析神器—时间复杂度

你要预测当n=10000的时候,这个程序会运行多长时间,你首先要知道程序的运行时间都花在哪了?

算法分析神器—时间复杂度

算法分析神器—时间复杂度

当电脑运行这段代码的时候,执行任何一条语句都需要花费时间,这是时间花费的主要地方

为了方便讨论,这里我们把每一条语句的执行时间都看做是一样的,记为一个时间单元

算法分析神器—时间复杂度

你看一下刚才的程序都有哪些语句

算法分析神器—时间复杂度

算法分析神器—时间复杂度

你看,这个程序有这么几个地方消耗了时间

① 蓝色框的两条语句,花费两个时间单元

②黑色框的一条语句,花费n+1个时间单元

③红色框的两条语句,花费2*n个时间单元

算法分析神器—时间复杂度

那么一共花费了3n+3个时间单元,可以看出,程序消耗的时间和你的n成线性关系

这不是数学吗,慧子心里想到

算法分析神器—时间复杂度

现在我用T(n)表示这个程序运行了多长时间,那么这个程序运行的时间就可以写成T(n)=3n+3

其中的n被我们称为问题的规模,其实就是你处理问题的大小

克顺手画了这个函数的图

算法分析神器—时间复杂度

本文主要讨论问题规模和运行时间的关系,假定不同输入和运行时间基本无关

哦,我懂了,要预测程序的时间,我可以把运行时间函数求出来

算法分析神器—时间复杂度

慧子

算法分析神器—时间复杂度

恩恩,对的

这个函数表达式看起来挺复杂的

算法分析神器—时间复杂度

慧子

算法分析神器—时间复杂度

我们常常会对这个函数进行简化,使得它既简单又不失函数的主要特性

哦?怎么简化

算法分析神器—时间复杂度

慧子

时间复杂度

算法分析神器—时间复杂度

我们一般只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项,也就是最高次项

比如说:T(n)=3n+3,当n非常大的时候常数3和n的系数3对函数结果的影响就很小了

算法分析神器—时间复杂度

算法分析神器—时间复杂度

所以一般我们会保留最高次项并忽略该项的系数

比如: 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)=3n+3,简化后T(n)~f(n)=n,那我们记为O(n)

更准确地说O代表了运行时间函数的一个渐进上界,即T(n)在数量级上小于等于f(n)

哦,原来时间复杂度可以表示某个算法的运行时间的趋势,大致地度量算法效率的好坏, 那我该如何算这个时间复杂度呢?

算法分析神器—时间复杂度

慧子

时间复杂度的计算

算法分析神器—时间复杂度

从前面可以总结出计算算法复杂度大O的方法

一、得出运行时间的函数 二、对函数进行简化

①用常数1来取代运行时间中所有加法常数

②修改后的函数中,只保留最高阶项 ③如果最高阶项存在且不是1,则忽略这个项的系数

算法分析神器—时间复杂度

举个例子吧,先来看这样一段代码

算法分析神器—时间复杂度

算法分析神器—时间复杂度

显然,T(n)=3,对这个函数进行简化,用常数1取代常数3,然后取代后的函数没有最高阶项,那么这个算法的时间复杂度就是O(1).

O(1)也被称为常数阶

每次都要把时间函数算出来,好复杂,有没有简便一点的方法

算法分析神器—时间复杂度

慧子

算法分析神器—时间复杂度

这个还真可以耍耍小聪明,一般来说,最内层执行次数最多的语句就决定了整个算法的趋势

算法分析神器—时间复杂度

算法分析神器—时间复杂度

你只要看看最内层的语句执行次数的规律就行了,这个内层打印语句随着问题规模n的增加会呈线性增加,直接就可以判定复杂度为O(n)

这个方法真棒,那么按照这个方法就很容易得出下面这个嵌套的两层for循环的复杂度为O(n^2)了

算法分析神器—时间复杂度

慧子

慧子随手写了一段嵌套循环的代码

算法分析神器—时间复杂度

算法分析神器—时间复杂度

恩恩,对的,最内层的语句随n的增加会呈二次函数的规律执行,代表了这个算法执行时间的一个趋势

我听说有一个很神奇的函数叫对数函数,它随着自变量的增大,因变量增长的很慢,这个应该很受欢迎吧

算法分析神器—时间复杂度

慧子

算法分析神器—时间复杂度

嗯嗯,对的,对数函数的趋势显然比线性函数好(对数函数随着自变量的增大因变量增长的很慢)

算法分析神器—时间复杂度

接着,克又写了一段时间复杂度为对数的代码

算法分析神器—时间复杂度

算法分析神器—时间复杂度

你看,这段代码的复杂度就为对数级别的,O(logn)

这个怎么分析

算法分析神器—时间复杂度

慧子

一向数学不太好的谦子此时有点懵

算法分析神器—时间复杂度

和之前的分析方法一样,我们着重看执行次数最多的内层代码语句

算法分析神器—时间复杂度

算法分析神器—时间复杂度

每循环一次,sum就给自身乘以2,乘了多少次就跳出循环了呢(大于等于n)?不知道,就设为x吧,那么2^x=n,解出x=logn,这说明随着n的增大,最消耗时间的内层语句是呈指数变化的

哦,我懂了,原来如此

算法分析神器—时间复杂度

慧子

算法分析神器—时间复杂度

复杂度的内容很多,你只要理解它的含义以及会分析简单的算法就行了,以后遇到复杂的,为师会给你传授的

好的

算法分析神器—时间复杂度

慧子

慧子与老师道了别

转载:

http://www.sohu.com/a/218317504_478315

今天的文章算法分析神器—时间复杂度分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/63119.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注