算法

开发工具与关键技术：数据结构基础
作者：
撰写时间：2020年4月28日

算法是解决问题的方法，是程序设计的精髓，程序设计的实质就是构造解决问题的算法。算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

有穷性:一个算法应包含有限个操作步骤。即一个算法在执行若干个步骤之后应该能够结束，而且每一步都在有限时间内完成。
确定性:算法中的每一步都必须有确切的含义，不能产生二义性。
可行性:算法中的每一个步骤都应该是能有效地执行，并得到确定的结果。
输入:所谓输入，是指在算法执行时，从外界取得必要的数据。计算机运行程序的目的是为了进行数据处理，在大多数情况下，这些数据需要通过输入得到。有些情况下，数据已经包含在算法中，算法执行时不需要任何数据，所以一个算法可以有零个或多个输入
输出:一个算法有一个或多个输出，这是算法进行数据处理后的结果。没有输出的算法是毫无意义的。
算法设计的好坏关乎程序的执行效率，算法的设计必须满足下列四个要求：
1：正确性 2：可读性 3：健壮性 4：效率与低存储量需求

算法的时间复杂度：一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。语句执行一次实际所需的具体时间是与机器的速度、编译程序质量、输入数据等密切相关，与算法设计的好坏无关。所以，可用算法中语句的执行次数来度量一个算法的效率。
首先定义算法中一条语句的语句频度，语句频度是指语句在一个算法中重复执行的次数。以下给出了两个n×n阶矩阵相乘算法中的各条语句以及每条语句的语句频度。

T(n)随n的增大而增大，增长得越慢，其算法的时间复杂度越低。下列三个程序段中分别给出了原操作count++的三个不同数量级的时间复杂度。

程序执行时，除了需存储本身所用的指令，常数，变量和输入数据以外，还需要一些对数据进行操作的辅助存储空间。 其中对于输入数据所占的具体存储量只取决于问题本身，与算法无关，这样只需要分析该算法在实现时所需要的辅助空间单元数就可以了。
算法的执行时间和存储空间的耗费是一对矛盾体，即算法执行的高效通常是以增加存储空间为代价的，反之亦然。不过，就一般情况而言，常常以算法执行时间做为算法优劣的主要衡量指标。