【数据结构】时间空间复杂度

怼烎@ 2023-02-20 12:22 152阅读 0赞

### 复杂度 ###

*  时间复杂度
 *   *  分析算法时间复杂度的基本方法：
     *  空间复杂度

# 时间复杂度 #

算法中基本操作重复执行的次数可以用n的某个函数 f(n)表示，因此算法的时间量度记作 T(n) = O(f(n))  
它表示，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

**若f(n)=amnm+am-1nm-1+…+a1n+a0是一个多项式，则T(n)=O(nm)。**（没咋懂）  
在计算复杂度时，可以忽略所有低次幂项和最高次幂的系数，由此简化算法分析。

## 分析算法时间复杂度的基本方法： ##

*  找出所有语句中语句频度最大的语句作为基本语句；
 *  计算基本语句的频度得到问题规模n的函数f(n)；
 *  取其数量级用符号“O”表示即可。

由于算法的时间复杂度考虑的只是对于问题规模n的增长率,所以有时可以不用精确计算其基本操作执行次数的情况下,只求出它关于n的增长率(也就是阶)即可。  
**例：**  
for (i=2; i<=n; ++i)  
for(j=2; j<=i-1; ++j) \{ ++x; a\[i\]\[j\]=x; \}  
语句== ++x == 的执行次数关于n的增长率为n2，它是语句频度表达式(n-1)(n-2)/2中增长最快的项，因此可以得出该程序段的时间复杂度为T(n)=O(n2)。

**例：**  
常量阶：\{x++; s=0;\} //T(n)=O(1)  
for(i=0;i<10000;i++)\{x++; s=0;\} //T(n)=O(1)  
线性阶：for(i=0;i<n;i++)\{x++; s=0;\} //T(n)=O(n)  
平方阶：x=0;y=0; for(k=1;k<=n;k++)x++;  
for(i=1;i<=n;i++)for(j=1;j<=n;i++)y++; //T(n)=O(n2)  
立方阶：x=1;  
for(i=1;i<=n;i++)for(j=1;j<=n;i++)for(k=1;k<=n;k++)x++;//T(n)=O(n3)  
对数阶：for(i=1;i<=n;i=i\*2)\{x++; s=0;\}//T(n)=O(log2n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70]

## 空间复杂度 ##

渐进空间复杂度作为算法所需存储空间的度量，简称空间复杂度，它也是问题规模n的函数，记作：S(n) = O(f(n))  
一般情况下，只分析算法所需的辅助空间就可以了，不考虑程序本身所占空间和输入数据所占空间。  
若所需辅助空间对于输入数据量而言是个常数，则称该算法为原地工作。  
**例：**  
for(i=0;i<n/2;i++)\{  
t=a\[i\];  
a\[i\]=a\[n-i-1\];  
a\[n-i-1\]=t;  
\}空间复杂度：O(1)

for(i=0;i<n;i++)b\[i\]=a\[n-i-1\];  
for(i=0;i<n;i++)a\[i\]=b\[i\];空间复杂度：O(n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020062622355214.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JsYWNrX0N1c3RvbWVy,size_16,color_FFFFFF,t_70