时间复杂度和空间复杂度

刺骨的言语ヽ痛彻心扉 2023-09-25 22:46 71阅读 0赞

**目录**

引入：算法的好与坏

渐进时间复杂度

空间复杂度

什么是空间复杂度？

空间复杂度的计算

--------------------

## **引入：算法的好与坏** ##

衡量算法的好与坏有很多量度，这之中最重要的两个量度就是**时间复杂度和空间复杂度。**

那么，何为时间复杂度和空间复杂度呢？让我们来看以下一个场景。

小陈和小宇来小米公司应聘，雷总给他们布置了一个项目，要求他们用代码实现出来。

过了几天他们都实现了需求，功能都差不多。

![878be402b4e541739eabeed3c0e8d453.jpeg][]  
![c82c528714e94a5ea3697640016fd6b3.jpeg][]

在上述场景中，小宇虽然也按照雷总的要求实现功能，但他的代码存在两个严重的问题。

**1.运行时间长**

运行小陈的代码只要100ms，而运行小宇的代码需要100s，使用者肯定是无法忍受的。

**2.占用空间大**

小陈的代码只消耗5MB内存，而小宇的代码却需要消耗500MB内存，这会给使用者造成很多麻烦。

**由此可见：运行时间长短与占用空间大小与程序的好坏密切相关。**

## 渐进时间复杂度 ##

若要分析代码的时间复杂度，我们先来引入**基本操作执行次数**这个概念。

比如现在面前有一个鸡腿，你需要三口才能吃完。我们不妨设n为吃的口数，那么有T（n）=3-n

当n为三时，恰好吃完。由此：**对于程序基本操作次数，有函数T（n）表示，n为输入规模。**

但有了T（n）之后，若要比较代码的运行时间还是有困难的。

例如算法S的执行次数时T（n）=10n²，算法Z的执行次数是T（n）=100n，这两个的运行时间还需要看n的取值。因此为了解决这一类问题，有了**渐近时间复杂度**这一概念。如下：

**我们通过计算得出一个算法的运行时间 T(n), 与T(n)同数量级的即幂次最高的O(F(n))即为这个算法的时间复杂度。例如：某算法的运行时间T(n) = n+10与n是同阶的（同数量级的），所以称T(n)=O(n)为该算法的时间复杂度。**

直白的讲：时间复杂度就是把程序的相对执行时间T（n）简化成一个数量级，可以是n，n²等。

如何推导出时间复杂度呢？有这几个原则：

如果运行的时间是常数量级，则用常数1表示。 eg.7--1.

只保留函数中的最高阶项。eg.n²+n--n²

如果最高阶项存在，则省去最高阶项前的系数。eg.8n--n.

在以后我们会学习到各种各样的时间复杂度如：1，lgn，n，n²，n！...

若要比较哪个更节省时间，可以通过函数图像，当n取值足够大时，不难得出：

O(1) < O(lgn) < O(n) < O(n²) < O(n!)，还有更多如下：

![2ff5c244994c4cc18fce6b3b5e46e449.jpeg][]

## 空间复杂度 ##

### 什么是空间复杂度？ ###

在运行一段程序时，我们不仅要执行各种运算指令，同时也会根据需要，存储一些中间数据，以便后续指令可以更方便地继续执行。

**但是，内存的空间有限，在时间复杂度相同的情况下，程序占用的空间自然是越小越好。如何描述占用空间的大小呢,这便用到了空间复杂度。**

**和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，同样使用了大O表示法。记作S(n)=O(f(n)),其中n为问题的规模，f(n)为算法所占存储空间的函数。**

### **空间复杂度的计算** ###

和时间复杂度类似，空间复杂度也有几种不同的增长趋势如：

1.**常量空间**：当算法的存储空间大小固定，和输入的规模没有直接联系时，空间复杂度记为O(1).

void main(int n){
        int var = 3;
        ...
    }

2.**线性空间**：当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模n成正比时，空间大小记为O(n).

void fun2(int n){
        int[] array = new int[n];
        ...
    }

3.**二维空间**：当算法分配的空间是一个二维数组的组合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记为O(n²).

void fun3(int n){
        int[][] matrix = new int[n][n];
        ...
    }

4.**递归空间：**递归比较特殊，它显然没有明显地声明变量与集合，但是计算机执行时，会专门分配一片内存，用来存储"**方法调用栈**"。

“方法调用栈”包括入栈和出栈这两个行为。

当进入一个新方法时，执行入栈，把调用的方法和参数压入栈中。

当方法返回时，执行出栈，把调用的方法和参数信息从栈中弹出。

下面有一个递归程序：

void fun4(int n){
        if(n <= 1)
            return;
        fun4(n-1);
        ...
    }

假如传入初始值n=3,那么方法fun4(参数n=3)的信息先入栈。

接下来递归用相同的方法（参数n=2）的信息调用入栈。

以此类推，递归越来越深，入栈元素越多。到n=1时，满足条件，方法出栈。

最终，“方法调用栈”全部元素都会出栈。

由此，执行递归操作所需要的内存空间和递归深度成正比。纯粹递归操作的空间复杂度也是线性的，如果递归深度是n，那么空间复杂度就是O(n).

好了，本次就讲到这里，希望你有所收获，如果你喜欢的话还请支

持哦。

[878be402b4e541739eabeed3c0e8d453.jpeg]: https://img-blog.csdnimg.cn/878be402b4e541739eabeed3c0e8d453.jpeg
[c82c528714e94a5ea3697640016fd6b3.jpeg]: https://img-blog.csdnimg.cn/c82c528714e94a5ea3697640016fd6b3.jpeg
[2ff5c244994c4cc18fce6b3b5e46e449.jpeg]: https://img-blog.csdnimg.cn/2ff5c244994c4cc18fce6b3b5e46e449.jpeg

发表评论取消回复

表情：

评论列表（有 0 条评论，71人围观）

还没有评论，来说两句吧...

相关阅读

相关空间复杂度和时间复杂度

时间复杂度和空间复杂度是衡量算法性能的关键指标。时间复杂度评估算法执行时间，空间复杂度评估内存消耗。本文将深入探讨它们的概念、计算方式以及如何优化算法以提高效率。复杂度分...

朴灿烈づ我的快乐病毒、/ 2024年04月23日 15:58/ 0 赞/ 75 阅读

相关时间复杂度和空间复杂度

如何衡量一个算法的好坏呢？方法：分析算法效率。算法效率分析分为两种：第一种是时间效率，时间效率被称为时间复杂度第二种是空间效率。空间效率被称作空间复杂度。时间复杂度主要衡...

Myth丶恋晨/ 2024年04月20日 14:25/ 0 赞/ 90 阅读

相关【时间复杂度和空间复杂度】

前言：首先介绍一下算法(Algorithm) 算法是对特定问题求解步骤的一种描述。一个“好”的算法应该达到以下目标：正确性、可读性、健壮性、高效率与低存储量需求算法的

悠悠/ 2024年02月20日 09:36/ 0 赞/ 62 阅读

相关时间复杂度和空间复杂度

一、什么是时间复杂度和空间复杂度？ 1、算法效率说到时间复杂度和空间复杂度，那么就不得不提及一下算法效率这个概念了，那么什么是算法效率呢？ > 算法效率分析分为

刺骨的言语ヽ痛彻心扉/ 2023年10月04日 21:34/ 0 赞/ 54 阅读

相关时间复杂度和空间复杂度

目录引入：算法的好与坏渐进时间复杂度空间复杂度什么是空间复杂度？空间复杂度的计算 -------------------- 引入：算法的好与坏衡

刺骨的言语ヽ痛彻心扉/ 2023年09月25日 22:46/ 0 赞/ 72 阅读

相关时间复杂度和空间复杂度

先说结论：常规的代码的算法时间复杂度是有规律的:看几重循环: 一重循环则为O(n)线性阶，二重循环为O(n^2) K方阶; 二分法则为O(logn)对数阶，二分例

Dear 丶/ 2023年01月18日 04:14/ 0 赞/ 175 阅读

相关时间复杂度和空间复杂度

一、时间复杂度 1、定义若存在函数，使得当趋向无穷大时，的极限值为不等于 0 的常数，则称是的同数量级函数，记作，称为算法的渐进时间复杂度，简称时间复

浅浅的花香味﹌/ 2022年11月12日 14:59/ 0 赞/ 271 阅读

相关时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可

秒速五厘米/ 2022年08月21日 02:27/ 0 赞/ 278 阅读

相关时间复杂度和空间复杂度

一、为什么要研究时间和空间复杂度假设计算机是无限快的并且计算机存储器是免费的的，你还有什么理由来研究算法吗？即使只是因为你还想证明你的解法会终止并以正确的答案终

灰太狼/ 2022年04月13日 08:17/ 0 赞/ 415 阅读

相关时间复杂度和空间复杂度

[https://blog.csdn.net/zxm490484080/article/details/72210501][https_blog.csdn.net_zxm490

待我称王封你为后i/ 2021年09月15日 09:46/ 0 赞/ 493 阅读