数据结构——时间复杂度&空间复杂度的区别用法_时间复杂度和空间复杂度的区别

目录：

一：时间复杂度：大 O 阶推导方法

1.定义 

推荐网址了解：

2.时间复杂度的计算 

3.举例：

4.分析：

5.常见的时间复杂度

二.空间复杂度

1.定义

2.空间复杂度的计算

计算方法： 

举例1：

举例2：

举例3：

3.需存储空间包括以下两部分

 （1）固定部分

（2）可变空间

 三：常用的算法的时间复杂度和空间复杂度

---

一：时间复杂度：大 O 阶推导方法

1.定义 

 时间复杂度所需消耗的时间即基本操作执行次数

推荐网址了解：

 一套图 搞懂“时间复杂度”

https://blog.csdn.net/qq_41523096/article/details/82142747

 

2.时间复杂度的计算 

（1）用常数 1 取代运行时间中的所有加法常数

（2）在修改后的运行次数函数中，只保留最高阶项

（3）如果最高阶项存在且不是 1，则去除与这个项相乘的常数（即 

O(2n^2) = O(n^2)

），得到的结果就是大 O 阶

3.举例：

int i,j;
for ( i = 0; i < n; ++i){
    for(j = i; j < n; ++j){
        /*时间复杂度为 O(1) 的程序步骤序列 */
    }
}

4.分析：

对于外循环，其时间复杂度为 O(n)；

对于内循环环，当 i=0 时，内循环执行了 n 次，当 i=1 时，执行了 n-1 次，······当 i=n-1 时，执行了 1 次。

因此内循环总的执行次数为：

n + (n-1) + (n-2) + \cdots + 1 = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}

根据大 O 阶推导方法，最终上述代码的时间复杂度为 ：

5.常见的时间复杂度

二.空间复杂度

1.定义

算法的空间复杂度通过计算算法所需的存储空间实现

即运行完一个程序所需内存的大小

 算法的时间复杂度和空间复杂度是可以相互转化的

2.空间复杂度的计算

利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计

一个算法所需的存储空间用f(n)表示

空间复杂度的计算公式记作：S(n)=O(f(n))　　
 
其中n为问题的规模
 
S(n)表示空间复杂度

计算方法： 

（1）忽略常数，用O(1)表示

举例1：

 
a = 0
b = 0
print(a,b
 
 
它的空间复杂度O（n）=O（1）；

 

（2）递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间 

举例2：

 
def fun(n):
    k = 10
    if n == k:
        return n
    else:
        return fun(++n)
递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O（n*1）=O（n)。

 

（3）对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数

         因为递归最深的那一次所耗费的空间足以容纳它所有递归过程

举例3：

temp=0;
for(i=0;i<n;i++):
    temp = i
 
变量的内存分配发生在定义的时候，因为temp的定义是循环里边，所以是n*O(1)
temp定义在循环外边，所以是1*O(1) 

 

 

一般情况下，一个程序在机器上执行时：

除了需要存储程序本身的指令，常数，变量和输入数据外

还需要存储对数据操作的存储单元的辅助空间

若输入数据所占空间只取决于问题本身，和算法无关

这样就只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O（1）

3.需存储空间包括以下两部分

 （1）固定部分

这部分属于静态空间

这部分空间的大小与输入/输出的数据的个数多少、数值无关

主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间

（2）可变空间

这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等

这部分的空间大小与算法有关

 三：常用的算法的时间复杂度和空间复杂度