（二）算法分析

（二）算法分析

专栏：​​数据结构与算法分析​​

上一篇： ​​（一）数据结构绪论​​

下一篇：

文章目录

​​1. 估计算法资源消耗所需​​

​​1.1 实验统计​​​​1.2 理论分析​​​​1.3 实验统计与理论分析​​

​​2. 算法复杂度​​

​​2.1 时间复杂度 (Time complexity)​​

​​2.1.1 一个简单的例子​​​​2.1.2 不同复杂度之间的对比​​

​​2.2 空间复杂度(Space complexity)​​

算法(algorithm) 是对特定问题的求解步骤的一种描述，是指令的有限序列，其中一条指令表示一个或多个操作。

根据算法编制的程序最终是要运行在计算机上，由计算机执行程序最终得出结果。所以我们需要考虑的是程序执行完毕得出结果需要多少时间，以及占用了多少资源（通常指占用内存）。   现在个人计算机的内存容量多数已经达到了4GB 和 8GB，而专门用于实验室的计算机，内存甚至已经达到了256GB以上。目前多数情况下，问题的规模不超过千万，足以存储，但是目前计算机的运行速度仍相对有限，特别当规模较大时，在执行时间上，不同效率的算法天差地别，有些算法只需要运行几秒就能得出答案，而另一种算法可能需要数千年。

目前来说，更为重视算法的运行时间，而不是内存空间占用大小。因此大规模问题的内存占用，现在的计算机基本上可以满足要求，并且内存并不是一次性消耗品，程序执行结束后，内存即可得到释放，并没有产生消耗。但是算法的运行时间则不同，不同效率的算法之间的差别过大，导致如果算法设计得不够好，即使小规模的问题，计算机仍需要数小时、数天来完成计算，当规模变得更大后，计算机在报废前完成计算都变成了奢望。   当然，也不是说内存空间占用就完全不需要理会，而是说目前的存储器容量在大规模问题上都可以满足大多数算法的需求，大多时候存在空闲空间，很少会出现需要远超于问题规模的存储空间的情况。反而是一般效率的算法，处理中等规模问题时很有可能做不到数秒内完成，所以一般是优先考虑运行时间，甚至为了更快还会以空间换时间。

1. 估计算法资源消耗所需

估计算法资源消耗所需，通常有两种方法，分别是实验统计和理论分析。

1.1 实验统计

实验统计 的方法是直接按照对应算法编写程序，然后分别记录不同规模的输入时程序所需的运行时间和占用空间。

这种方式虽然可以得到较为准确的运行时间和占用空间数据，但是需要由算法编写出相应的程序并在机器上运行，比较费时间。对于同一个算法，使用不同的编程语言编写或者同一个编程语言使用不同的实现也会对运行时间造成影响。同时，计算机硬件配置不同，运行速度有快有慢，得到的数据也只能作为参考，并不说明在其它机器上也消耗这么多资源。   对实验统计得到的数据进行拟合，可以得到算法所需资源消耗与问题规模的关系。

1.2 理论分析

理论分析方法则是直接根据算法或相关代码来得到运行时间与问题规模大小的关系。

理论分析的方法仅仅是得到资源消耗与问题规模大小之间的关系，并非是实际时间数据，因此，要估算出算法所需的资源消耗，还需要在计算机上运行实际程序，得到输入在某个规模大小时对应时间值和占用空间大小，以此推算出算法在不同问题规模下所需的相应资源消耗。

理论分析方法得到的资源消耗与问题规模大小之间的关系，在不同的设备上，不同的环境都通用，可以借此来对算法的好坏做一个评估。

1.3 实验统计与理论分析

实验统计和理论分析方法各有优势。理论分析较为简便，通用性好，但无法得到实际数据，只能估算。实验统计方法耗时久，受环境因素影响大，但针对性强。   当程序实际运行环境确定后，实验统计方法得到的数据更接近实际，并且可以用来验证理论分析所得出结果。所以通常采用理论结合实际的方式，在理论分析完毕后进行实验统计，不仅可以验证算法的正确性，还能防止意料情况的发生（如问题达到一定规模后，占用内存超出设备内存容量等）。

2. 算法复杂度

算法复杂度 即算法所需资源与数据规模之间的增长关系，分为 时间复杂度 和 空间复杂度。

2.1 时间复杂度 (Time complexity)

算法总是假定运行在计算机上，但是并不指定计算的性能。为了便于分析，我们把计算机执行一条简单指令或执行由数条简单指令构成的复合指令的时间都定为1。

相当于如果两条语句分别是执行一次加法和执行3次乘法，它们的运行时间认为是相同的，这么做是为了简化分析。分析时先得出简单的关系，如果有必要，再进行细致的分析。

下面我们尝试对一个实现的简单算法分析其运行时间与数据规模大小之间的关系。

2.1.1 一个简单的例子

int partialSum(int N){ int sum = 0; //1. 初始化，执行1次， 运行时间算作 1 for (int i = 1; i <= N; i++) //2. 循环，执行N+1次，运行时间算作 N+1 sum += i * i * i; //3. 执行N次， 运行时间算作 N return sum; //4. 执行1次， 运行时间算作 1}

函数中的代码一共4句，由于我们将语句的运行时间计算简化，所以对于有固定数量指令组成的顺序语句（第1句和第4句），运行时间都算作1，而循环语句我们则根据其执行的次数计算。

第1句执行 1 次，运行时间算作 1第2句循环执行N+1次（i从1开始，等于N+1时不符合循环条件退出，共N+1次），运行时间算作 N+1第3句循环执行N次（ i 从1开始，共计算到N），运行时间算作 N第4句执行 1 次，运行时间算作 1

2.1.2 不同复杂度之间的对比

2.2 空间复杂度(Space complexity)

空间复杂度只计算额外需要的内存空间，原本数据元素所占的内存空间大小不计算在内。

专栏：​​数据结构与算法分析​​

上一篇： ​​（一）数据结构绪论​​

下一篇：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。