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

你的名字 2023-02-26 07:24 210阅读 0赞

算法的衡量指标：在正确性的前提下，重点关注以下指标:

（1）时间性能——运行算法所需的时间开销。

（2）空间性能——运行算法所需的辅助空间的规模。

（3）其它性能——如可读性/可移植性等。

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

### 时间复杂度 ###

时间性能（时间复杂度）的描述方法讨论：

方式(1)： 以运行算法的机器时间开销来度量

问题：与具体机器相关，难以比较

方式（2）：以算法中语句的执行次数来衡量

问题：计算麻烦，可以简化为

方式（3）：以算法中语句的执行次数的数量级来替代。    √**  **

**数量级：如果变量n的函数f(n)和g(n)满足：**

lim f(n)/g(n)=常数 k (k≠∞,0)，

则称f(n)和g(n) 是同一数量级的，

并用f(n)=O(g(n))的形式来表示。

较为常见的算法的时间复杂度从小到大依次如下：![20200714175817663.png][]

例：求解以下程序段的时间复杂度：

for（i=1; i<=n; i++）x=x+1;

该语句的流程图如下:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

由此可知，数量级为：limf(n)/g(n)= lim(3n+2)/n = 3，

相应的时间复杂度为为O (n)

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

### 空间复杂度 ###

——计算方法类似时间复杂度![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

[20200714175817663.png]: /images/20230209/c086766175ff47b9913be86bf5772c1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20230209/74fc19d4c7144821bae98b0f87dfe142.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20230209/019804fbf97e450091f1ba5ded06ce73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20230209/d125b87734914439b01c64d1bdae3ddc.png