算法的时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度

• 前言
• 一，算法效率
• • 1.1 如何衡量一个算法的好坏
  • 1.2 算法的复杂度
• 二，时间复杂度
• • 2.1 时间复杂度的概念
  • 2.2 大O渐进表示法
• 三，空间复杂度
• • 3.1 空间复杂度的概念
  • 3.2 大O渐进表示法
• 四，常见时间复杂度和空间复杂度

前言

嗨，我是firdawn，本章将简单介绍，算法的时间复杂度和空间复杂度的概念，如何用大O渐进表示法估算，以及它们的计算，下面的图是本章的思维导图，那么，让我们开始吧！ ​​​

一，算法效率

1.1 如何衡量一个算法的好坏

现在有一个使用递归方式实现斐波那契数列的函数如下图1.1-1，函数的算法非常简洁，但是，简洁的算法就一定是好的算法吗？我们使用函数时会发现，当n只是大于等于50时，这个函数输出结果时，我们就需要等待很久的时间，所以，简洁的算法不一定的好的算法。那么我们应该如何衡量算法的好与坏呢？

1.2 算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。 不过，由于计算机行业的迅速发展，单位存储容量的设备价格已经十分廉价，所以一般来说，空间对于我们来说是相对富足的，我们如今已经不需要特别关注一个算法的空间复杂度，而是更在意一个算法的时间复杂度。

二，时间复杂度

2.1 时间复杂度的概念

算法的时间复杂度是一个函数，它定量描述了算法执行消耗的时间。不过，算法执行消耗的具体时间是无法计算出来的，因为这不仅与你的代码质量有关，而且与运行程序的系统以及设备种类等诸多因素有关。而一个算法所花费的时间与语句的执行次数成正比，所以，我们一般 用算法中的基本操作的执行次数，表示算法的时间复杂度

我们用一些例题来解释时间复杂度的概念。第一题： 下图1.2-1为使用循环计算斐波那契数列的函数，他的时间复杂度是多少呢？ 当n<=2时，图1.2-1的算法中，函数不进入循环，算法只执行一次，但当n很大时，算法会执行n-2次，那么该算法的时间复杂度是多少呢？其实呀，我们在计算算法的时间复杂度时，采用的是保守的估计，也就是使用该算法的最大执行次数作为该算法的时间复杂度。所以它的时间复杂度是：n-2

第二题： 计算Func4的时间复杂度，题目为图2.1-2。 图2.1-2中，函数执行了100次，所以它的时间复杂度为：100

第三题： 计算Func5的时间复杂度，题目为图2.1-3。 图2.1-3中，函数最快执行n次，最慢执行 (n*(n+1))/2 次，时间复杂度计算的是保守次数，所以该函数的时间复杂度为： (n*(n+1))/2

第四题： 计算Func6的时间复杂度，题目为图2.1-4。 图2.1-4中，函数最好执行1次，最坏执行log₂n

2.2 大O渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号 推导大O阶方法： 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中，只保留最高阶项。 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

需要注意的是，有些算法的时间复杂度存在最好、平均和最坏情况： 最坏情况：任意输入规模的最大运行次数(上界) 平均情况：任意输入规模的期望运行次数 最好情况：任意输入规模的最小运行次数(下界) 例如：在一个长度为N数组中搜索一个数据x 最好情况：1次找到 最坏情况：N次找到 平均情况：N/2次找到 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

三，空间复杂度

3.1 空间复杂度的概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

3.2 大O渐进表示法

空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。 注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

让我们使用一些例子来解释时间复杂度。题目一： 图2.1-3中，函数的空间复杂度是多少呢？答：图2.1-3中使用了常数个额外空间，所以空间复杂度为O(1)

**题目二：**在图3.2-1中，函数的空间复杂度是多少呢？ 在图3.2-1中，函数动态开辟了n个空间，空间复杂度为O(N)

四，常见时间复杂度和空间复杂度

一般算法常见的复杂度如下：