时间复杂度

CDA老师1

--- # 时间复杂度 ## 算法的好与坏 **时间复杂度和空间复杂度究竟是什么呢?首先,让我们来想象一个场景。** **某一天,A和B同时加入了同一家公司。一天后,A和B交付了各自的代码,两人的代码实现的功能差不多。** **A的代码运行一次要花100ms,占用内存5MB。** **B的代码运行一次要花100s,占用内存500MB。** **1.运行时间长运行别人的代码只要100ms,而运行B的代码则要100s,使用者肯定是无法忍受的。** **2.占用空间大别人的代码只消耗5MB的内存,而B的代码却要消耗500MB的内存,这会给使用者造成很多麻烦。** **由此可见,运行时间的长短和占用内存空间的大小,是衡量程序好坏的重要因素。** **可是,如果代码都还没有运行,我怎么能预知代码运行所花的时间呢?** **由于受运行环境和输入规模的影响,代码的绝对执行时间是无法预估的。** **但我们可以预估代码的基本操作执行次数。** ## **基本操作执行次数** **关于代码的基本操作执行次数,下面用生活中的4个场景来进行说明。** **场景1 给B 1个长度为10cm的面包,B每3分钟吃掉1cm,那么吃掉整个面包需要多久?** **答案自然是3×10即30分钟。** **如果面包的长度是 **n** cm呢?此时吃掉整个面包,需要3乘以 **n** 即 3**n**分钟。** **如果用一个函数来表达吃掉整个面包所需要的时间,可以记作**T(n)**=3**n**,**n**为面包的长度。** **场景2 给B 1个长度为16cm的面包,B每5分钟吃掉面包剩余长度的一半,即第5分钟吃掉8cm,第10分钟吃掉4cm,第15分钟吃掉2cm……那么B把面包吃得只剩1cm,需要多久呢?** **这个问题用数学方式表达就是,数字16不断地除以2,那么除几次以后的结果等于1?** **这里涉及数学中的对数,即以2为底16的对数 **log_216** 。(注:下文中,对数函数的底数全部省略。)** **因此,把面包吃得只剩下1cm,需要5×log16即20分钟。** **如果面包的长度是 **n** cm呢?** **此时,需要5乘以log**n**即5log**n**分钟,记作**T(n)**=5log**n**。** **场景3 给小灰1个长度为10cm的面包和1个鸡腿,小灰每2分钟吃掉1个鸡腿。那么小灰吃掉整个鸡腿需要多久呢?** **答案自然是2分钟。因为这里只要求吃掉鸡腿,和10cm的面包没有关系。** **如果面包的长度是**n** cm呢?** **无论面包多长,吃掉鸡腿的时间都是2分钟,记作**T(n)**=2。** **场景4 给B 1个长度为10cm的面包,B 吃掉第1个1cm需要1分钟,吃掉第2个1cm需要2分钟,吃掉第3个1cm需要3分钟……每吃1cm所花的时间就比吃上一个1cm多用1分钟。那么B吃掉整个面包需要多久呢?** **答案是从1累加到10的总和,也就是55分钟。** **如果面包的长度是**n**cm呢?** **根据高斯算法,此时吃掉整个面包需要1+2+3+…+(**n**-1)+**n**即(1+**n**)×**n**/2分钟,** **也就是**0.5n^2+0.5n**分钟,记作**T(n)**=**0.5n^2+0.5n**。怎么除了吃还是吃啊?这还不得撑死?** **上面所讲的是吃东西所花费的时间,这一思想同样适用于对程序基本操作执行次数的统计。** **设**T(n)**为程序基本操作执行次数的函数(也可以认为是程序的相对执行时间函数),**n**为输入规模,刚才的4个场景分别对应了程序中最常见的4种执行方式。** **场景1 **T(n)**=3**n**,执行次数是线性的。** ``` def eat1(n): for i in range(n): print('等待1min') print('等待1min') print('吃1cm面包') ``` **场景2 **T(n)**=5log**n**,执行次数是用对数计算的。** ``` def eat2(n):    while n >1: print('等待1min') print('等待1min')        print('等待1min')        print('等待1min') print('吃1cm面包')        n /=2 ``` **场景3 **T(n)**=2,执行次数是常量。** ``` def eat3(n): print('等待1min') print('吃一个鸡腿') ``` **场景4 **T(n)**=**0.5n^2+0.5n**,执行次数是用多项式计算的。** ``` def eat4(n): for i in range(n): for j in range(i): print('等待1min') print('吃1cm面包') ``` ## 渐进时间复杂度 **有了基本操作执行次数的函数**T(n)**,是否就可以分析和比较代码的运行时间了呢?还是有一定困难的。** **例如,算法A的执行次数是**T(n)**=100**n**,算法B的执行次数是**T(n)**=**5n^2**,这两个到底谁的运行时间更长一些呢?这就要看n的取值了。** **因此,为了解决时间分析的难题,有了渐进时间复杂度(asymptotic time complexity)的概念,其官方定义如下:** **若存在函数**f(n)**,使得当n趋近于无穷大时,**T(n)**/**f(n)**的极限值为不等于零的常数,则称**f(n)** 是 **T(n)**的同数量级函数。记作**T(n)** = **O(f(n))**,称为**O(f(n))**,O为算法的渐进时间复杂度,简称为时间复杂度。** **因为渐进时间复杂度用大写O来表示,所以也被称为大O表示法。** **这个定义好晦涩呀,看不明白。** **直白地讲,时间复杂度就是把程序的相对执行时间函数**T(n)**简化为一个数量级,这个数量级可以是**n**、**n^2**、**n^3**等。** **如何推导出时间复杂度呢?有如下几个原则:** **• 如果运行时间是常数量级,则用常数1表示。** **• 只保留时间函数中的最高阶项。** **• 如果最高阶项存在,则省去最高阶项前面的系数。** **让我们回头看看刚才的4个场景。** **场景1 **T(n)**=3**n**,最高阶项为3**n**,省去系数3,则转化的时间复杂度为:**T(n)**= **O(n)**。** ![image20221122155640717.png](/z_anli/upload/pgc/202212/c9b3984494b8199e95431c383258032e.png) **场景2 **T(n)**=5log**n**,最高阶项为5log**n**,省去系数5,则转化的时间复杂度为:**T(n)**=O(log**n**)。** ![image20221122155801335.png](/z_anli/upload/pgc/202212/4f327a8107f058843abb8ab60e635eae.png) **场景3 **T(n)**=2,只有常数量级,则转化的时间复杂度为:**T(n)**=O(1)。** ![image20221122155908721.png](/z_anli/upload/pgc/202212/984be0ca46f76726ce6fcfcd0b91df5b.png) **场景4 **T(n)**=**0.5n^2+0.5n**,最高阶项为**0.5n^2**,省去系数0.5,则转化的时间复杂度为:**T(n)**=O(**n^2**)。** ![image20221122155959102.png](/z_anli/upload/pgc/202212/fa470a77f73eb301fd22ee84390aedbb.png) **这4种时间复杂度究竟谁的程序执行用时更长,谁更节省时间呢?** **当n的取值足够大时,不难得出下面的结论:O(1)
0.3639 8 0 关注作者 收藏 2022-12-20   阅读量: 482

评论(0)


暂无数据