算法效率评估

type

status

date

slug

summary

算法的定义

算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性。

问题是明确的，包含清晰的输入和输出定义。

具有可行性，能够在有限步骤、时间和内存空间下完成。

各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。

数据结构定义

数据结构（data structure）是组织和存储数据的方式，涵盖数据内容、数据之间关系和数据操作方法，它具有以下设计目标。

空间占用尽量少，以节省计算机内存。

数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。

提供简洁的数据表示和逻辑信息，以便算法高效运行。

数据结构设计是一个充满权衡的过程。如果想在某方面取得提升，往往需要在另一方面作出妥协。下面举两个例子。

链表相较于数组，在数据添加和删除操作上更加便捷，但牺牲了数据访问速度。

图相较于链表，提供了更丰富的逻辑信息，但需要占用更大的内存空间。

数据结构与算法的关

数据结构与算法高度相关、紧密结合，具体表现在以下三个方面。

数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。

算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。

算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。

在算法设计中，我们先后追求以下两个层面的目标。

找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。

寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。

也就是说，在能够解决问题的前提下，算法效率已成为衡量算法优劣的主要评价指标，它包括以下两个维度。

时间效率：算法运行时间的长短。

空间效率：算法占用内存空间的大小。

简而言之，我们的目标是设计“既快又省”的数据结构与算法。而有效地评估算法效率至关重要，因为只有这样，我们才能将各种算法进行对比，进而指导算法设计与优化过程。

效率评估方法主要分为两种：实际测试、理论估算。

实际测试

假设我们现在有算法 A 和算法 B ，它们都能解决同一问题，现在需要对比这两个算法的效率。最直接的方法是找一台计算机，运行这两个算法，并监控记录它们的运行时间和内存占用情况。这种评估方式能够反映真实情况，但也存在较大的局限性。

一方面，难以排除测试环境的干扰因素。硬件配置会影响算法的性能表现。比如一个算法的并行度较高，那么它就更适合在多核 CPU 上运行，一个算法的内存操作密集，那么它在高性能内存上的表现就会更好。也就是说，算法在不同的机器上的测试结果可能是不一致的。这意味着我们需要在各种机器上进行测试，统计平均效率，而这是不现实的。

另一方面，展开完整测试非常耗费资源。随着输入数据量的变化，算法会表现出不同的效率。例如，在输入数据量较小时，算法 A 的运行时间比算法 B 短；而在输入数据量较大时，测试结果可能恰恰相反。因此，为了得到有说服力的结论，我们需要测试各种规模的输入数据，而这需要耗费大量的计算资源。

理论估算

由于实际测试具有较大的局限性，因此我们可以考虑仅通过一些计算来评估算法的效率。这种估算方法被称为渐近复杂度分析asymptotic complexity analysis，简称复杂度分析。

复杂度分析能够体现算法运行所需的时间和空间资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。这个定义有些拗口，我们可以将其分为三个重点来理解。

“时间和空间资源”分别对应时间复杂度time complexity和空间复杂度space complexity。

“随着输入数据大小的增加”意味着复杂度反映了算法运行效率与输入数据体量之间的关系。

“时间和空间的增长趋势”表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的“快慢”。

复杂度分析优势。

它无需实际运行代码，更加绿色节能。

它独立于测试环境，分析结果适用于所有运行平台。

它可以体现不同数据量下的算法效率，尤其是在大数据量下的算法性能。

复杂度分析为我们提供了一把评估算法效率的“标尺”，使我们可以衡量执行某个算法所需的时间和空间资源，对比不同算法之间的效率。

📎

本文摘抄自Hello 算法