【数据结构和算法】3~5 时间复杂度和空间复杂度

矫情吗；* 2022-04-14 04:06 251阅读 0赞

# 算法效率的度量方法 #

容易想到的方法是：把算法跑若干次，然后拿个计时器在旁边计时。这种方法被称为“事后诸葛亮”方法，也称为事后分析估算方法。

事前分析估算方法：在计算机程序比编写前，依据统计方法对算法进行估算。

通过总结，我们发现，一个高级语言编写程序在计算机上运行所消耗的时间取决于下列因素：

（1）算法采用的策略，方案；

（2）编译产生的代码质量；

（3）问题的输入规模；

（4）机器执行指令的速度；

由上，抛开计算机硬件、软件因素，一个程序运行时间依赖于算法的好坏和问题输入的规模；

**高斯求和算法：1+2+...+n的问题**

算法1

int i, sum = 0, n = 100; // 执行1次
 for( i=1; i <= n; i++ ) // 执行了n+1次
 {
 sum = sum + i; // 执行n次
 }

算法2：

int sum = 0, n = 100;     // 执行1次
    sum = (1+n)*n/2;          // 执行1次

如果我们把循环看做一个整体，忽略头尾判断的开销，那么这两个算法其实就是n和1的差距；

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

# 函数的渐近增长 #

假设两个算法的输入规模都是n，算法A要做2n+3次操作，你可以这么理解：先执行n次的循环，执行完成后再有一个n次的循环，最后有3次运算。

算法B要做3n+1次操作，理解同上，你觉得它们哪一个更快些呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70][]

函数的渐近增长：

函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)；

第二个测试，算法C是4n+8，算法D是2n^2+1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70 1][]

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

# 算法的时间复杂度 #

定义：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T（n）=0（f（n））。它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。

关键：执行次数==时间

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

# 推导大O阶方法 #

如何分析一个算法的复杂度呢？如何推导大O阶呢？有以下攻略：

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

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

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

常见的时间复杂度：

<table> 
 <tbody> 
 <tr> 
 <td style="background-color:#b2c1db;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> 例子 </td> 
 <td style="background-color:#b2c1db;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> 时间复杂度 </td> 
 <td style="background-color:#b2c1db;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> 装逼术语 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> 5201314 </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> O(1) </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> 常数阶 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> 3n+4 </td> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> O(n) </td> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> 线性阶 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> 3n^2+4n+5 </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> O(n^2) </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> 平方阶 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> 3log(2)n+4 </td> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> O(logn) </td> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> 对数阶 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> 2n+3nlog(2)n+14 </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> O(nlogn) </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> nlogn阶 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> n^3+2n^2+4n+6 </td> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> O(n^3) </td> 
 <td style="background-color:#f2f4f8;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> 立方阶 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:187pt;"> 2^n </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:170pt;"> O(2^n) </td> 
 <td style="background-color:#e4e9f1;border-color:#ffffff;text-align:center;vertical-align:middle;width:198pt;"> 指数阶 </td> 
 </tr> 
 </tbody> 
</table>

有图有真相：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70 3][]

常用的时间复杂度所耗费的时间从小到大依次是：O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

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

# 算法的空间复杂度 #

算法的空间复杂度通过计算算法所需的**存储空间实现**，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

通常，我们都是用“时间复杂度”来指运行时间的需求，是用“空间复杂度”指空间需求。

当直接要让我们求“复杂度”时，通常指的是时间复杂度。

显然对时间复杂度的追求更是属于算法的潮流

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

★ finished by songpl  2018.11.24

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70]: /images/20220414/8cebeb20353748c6b19b53f5b7dd31f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70 1]: /images/20220414/5883a5b66db14aaebb9c1b4cd0b50279.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70 2]: /images/20220414/d3a8c88c2899490a864b1f25ea8e8b49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BsU29uZ19DU0RO_size_16_color_FFFFFF_t_70 3]: /images/20220414/5efa5f7cfb9547789a7829561b6af95d.png