算法及时间/空间复杂度的分析

分手后的思念是犯贱 2023-05-21 15:17 41阅读 0赞

## 算法（Algorithm） ##

**对特定问题求解步骤的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列**

##### 算法的基本特征 #####

①输入：有零个或多个输入  
②输出：有一个或多个输出  
③有穷性：在执行有穷步之后结束，且每一步都在有穷时间内完成  
④确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出  
⑥可行性：算法描述的操作可以通过已经实现的基本操作执行有限次完成

##### 有效算法五大特征 #####

①正确性：能满足具体问题的需求，对于任何合法的输入，算法都会得出正确的结果  
②健壮性：对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出相应处理，而不是产生错误结果或陷入瘫痪  
③可读性：容易理解和实现  
④时间效率高：运行时间短  
⑤空间效率高：占用的存储空间尽量少

##### 算法的描述方法（以欧几里得算法为例） #####

①自然语言  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]  
②程序流程图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]

③伪代码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]

④程序设计语言  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]

## 时间复杂度 ##

##### 渐进复杂度分析 #####

①算法的运行时间是问题规模n的函数，记作T(n)  
②用基本语句的执行次数表示T(n)  
③忽略低阶项和常系数，只考虑最高阶  
④用大O、大Ω和大Θ表示其渐近意义下的阶

##### 分析算法时间复杂度的一般步骤 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]

##### 渐进上界（O） #####

如果存在两个正的常数c和n0：  
对于任意n≥n0，都有f(n)≤c×g(n)，则称f(n)=O(g(n))，即g(n)为f(n)的上界  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]  
**一个算法的运行时间用大O符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑上界”或“紧确上界”**  
**一般地，如果f(n)=amnm\+am-1nm-1\+…+a1n+a0，有f(n)=O(nm)**

##### 渐进下界（Ω） #####

若存在两个正的常数c 和n0：  
对于任意n≥n0，都有f(n)≥c×g(n)，则称f(n)=Ω(g(n))，即g(n)为f(n)的下界  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]  
**一个算法的运行时间用大Ω符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”**  
**一般地，如果f(n)=amnm\+am-1nm-1\+…+a1n+a0，有f(n)=Ω(nm)**

##### 渐进紧界（Θ） #####

若存在三个正的常数c1、c2和n0：  
对于任意n≥n0都有c1×g(n)≥f(n)≥c2×g(n)，则称f(n)=(g(n))，即g(n)与f(n)同阶  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 7]  
**f(n)=Θ(g(n))，当且仅当f(n)=O(g(n))，f(n)=Ω(g(n))**  
**一般地，如果f(n)=amnm\+am-1nm-1\+…+a1n+a0，有f(n)=Θ(nm)**

##### 常见复杂度的大小 #####

<table> 
 <thead> 
  <tr> 
   <th>类型</th> 
   <th>顺序</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>多项式阶算法（有效算法）</td> 
   <td>T(n)=O(n<sup>k</sup>)</td> 
  </tr> 
  <tr> 
   <td>常见的多项式阶大小排序</td> 
   <td>O(1)&lt;O(log<sub>2</sub>n)&lt;O(n)&lt;O(nlog<sub>2</sub>n)&lt;O(n<sup>2</sup>)&lt;O(n<sup>3</sup>)</td> 
  </tr> 
  <tr> 
   <td>指数阶算法</td> 
   <td>T(n)= Ω(a<sup>n</sup>)，a&gt;1</td> 
  </tr> 
  <tr> 
   <td>常见的指数阶大小排序</td> 
   <td>O(2<sup>n</sup>)&lt;O(n!)&lt;O(n<sup>n</sup>)</td> 
  </tr> 
 </tbody> 
</table>

如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 8]  
运行时间表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 9]

##### 渐进时间复杂度分析的一般步骤 #####

①决定用哪个或哪些参数作为算法规模问题的度量  
②找出算法中的基本语句（循环体）  
③检查基本语句的执行次数是否依赖于其它影响（如排序问题中原序，可分为最好、最坏和平均）  
④建立基本语句执行次数的求和表达式  
⑤使用渐进符号O表示算法增长率的上限

Ps：通常只求最坏情况运行时间，因为  
给出了任何输入的运行时间的上界；对某些算法，最坏情况经常出现；“平均情况”往往与最坏情况一样差

## 空间复杂度 ##

**一个算法的存储量包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时，只考察临时变量所占空间**

##### 渐进空间复杂度 #####

同时间复杂度，S(n) = O(n)、Ω(n)、Θ(n)

##### 原地工作 #####

如果算法所需的辅助空间相对于问题的输入规模来说是一个常数，我们称此算法为原地（或就地）工作，即S(n) = O(1)

##### 递归 #####

对于递归函数的，需要空间（栈）来存储每一层的数据，因此空间复杂度并不为O(1)

## 递归方程及其求解方法 ##

##### 递归方程 #####

①递归方程是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数  
②当一个算法包含对其自身的递归调用时，可以用递归方程来表示其运行时间

##### 1）、迭代法 #####

**从初始递归方程开始，反复用递归方程右边的等式代入左边的函数，直到得到初值**  
例，求解：  
T(n) = O(1) 当n=1时  
T(n) = 2T(n/2)+ O(n) 当n>1时  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 10]

##### 2）、代入法 #####

①猜测解的形式  
②用数学归纳法进行验证

##### 3）、递归树法 #####

以树的形式来展开一个递归算法的模型：  
递归树是一棵结点带权值的树，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用

**①递归树的构造**  
初始的递归树只有一个结点，它的权标记为T(n)；然后按照递归树的迭代规则不断进行迭代，每迭代一次递归树就增加一层，直到树中不再含有权值为函数的结点  
**②递归树的求解**  
将树中每层中的代价求和，得到每层代价，再将所有层的代价求和，得到总的递归调用代价

例，求解：T(n)=2T(n/2)+O(n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 11]对于不平衡的递归树：T(n)=T(n/3)+T(2n/3)+n  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 12]  
设从根结点到最长路径的层数为：k  
则n\*(2/3)k = 1，解得 k = log3/2n  
得出时间复杂度为：  
![在这里插入图片描述][20200417163313587.png]

##### 4）、主方法 #####

适用于求解：  
T(n)=aT(n/b)+f(n) a≥1，b>1为常数，f(n)为渐近正函数

对原始方程进行解析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 13]

**分为三种情况**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 14]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: /images/20230521/98a8ea1b23544a69b649d443710c909e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: /images/20230521/ad6acbacfcdd43cfb6f72d07ca4b222b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]: /images/20230521/388b5a6e2ad845f29efbf3410432c22d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]: /images/20230521/d3489aa98cf74d36ac868c8de105a587.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]: /images/20230521/6f94d5618a3243818f17b19461f62415.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]: /images/20230521/bf7e438a38b841b1ab8fa64c3779b6ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]: /images/20230521/47cf3881ee8441ea98362cf9d53057bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 7]: /images/20230521/34e48d6bd6f441d3ba8c8c7ad276e973.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 8]: /images/20230521/76b6142df8694248a8d2e4948e90b8ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 9]: /images/20230521/6c4e5114ea5f429a901590a7b544c5d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 10]: /images/20230521/758dc4d247164690ba8d83b0383ab9af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 11]: /images/20230521/f7a64902f6b2435db94454b8832a2c61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 12]: /images/20230521/5aa8b402cf6e4ca682018fd832655c75.png
[20200417163313587.png]: /images/20230521/5e704449739f4a148c57f1f744c606ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 13]: /images/20230521/5900dfa0481847b7b4468c5771bedf29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 14]: /images/20230521/4f0691eb8df14a5fbb4e8cb0f5898847.png