---
# 时间复杂度
## 算法的好与坏
**时间复杂度和空间复杂度究竟是什么呢?首先,让我们来想象一个场景。**
**某一天,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)
暂无数据