解决问题：比较算法
算法是解决特定问题的分步指令集，重要的是要理解同一个问题可以用多种算法来解决。
规范的这一部分关注的是用于从针对同一问题的一组算法中选择最适合给定问题集的算法的标准。
换句话说，如何衡量给定算法的效率，以便将其与解决同一问题的不同算法进行比较？
一个非常常见的问题是在一组项目中搜索一个项目。这可能是在非常大的数据库中搜索一个人的姓名。
下面说明了解决此问题的一种算法
[此处将跟随线性搜索流程图的图像]
[此处将跟随 Python 实现的链接]
下面说明了另一种解决同一问题的算法。
[此处将添加二进制搜索流程图的图像]
[此处将添加 Python 实现的链接]
两种算法都解决了同一个问题。应该选择哪一个算法来作为程序编码以解决问题？
为了决定选择哪种算法而不是另一种算法，它们在效率方面进行了比较：找到解决方案所需的时间以及在此过程中消耗的资源。考虑不同汽车之间的选择，你可能会考虑从一个目的地到另一个目的地的行驶速度和旅途中的燃油消耗量。
也就是说，算法在终止并得出正确解决方案之前将占用多少（内存）空间。
为了识别空间效率，我们需要查看算法运行时使用的结构化数据量。在考虑空间效率时，目标是利用占用内存最少的结构化数据。
示例
- 用类型为real的变量填充列表在空间效率方面会很低，当很明显只需要整数（整数）来解决问题时。
- 用长度为 1000 初始化数组在空间效率方面会很低，当很明显要存储的最大元素为 100 时。
这是算法终止并得出正确解决方案所需的时间。
任何时间度量都将取决于其他因素，例如
- 用于实现算法的特定版本和类型的编程语言；
- 实现将运行的硬件规格；
- 当然还有算法的输入，例如，搜索非常大的集合将比搜索较小的集合花费更长的时间，并且搜索不存在于集合中的项目将比搜索存在于给定集合中的项目花费更长的时间。
显然，在比较不同算法时，将这些依赖关系降至最低非常重要。所使用的编程语言和硬件都会随着时间的推移而发生变化。因此，人们普遍认为任何比较都不应将这些因素考虑在内。
这使我们只剩下输入的大小作为我们希望在考虑算法终止并得出正确答案所需的时间时允许的唯一依赖项。
换句话说，我们想要找到一个函数 f(n)，其中 n 是输入的大小，例如要搜索的列表的长度。该函数使用算法终止所需的计算步骤数。
为了消除依赖性，在计算效率时，只考虑以下步骤
- 内存访问 - 也就是说任何内存查找，例如调用变量
- 分配
- 任何算术表达式
- 比较
|
与算法比较相关的疑问 考虑以下算法 number1 <- 输入 number2 <- 输入 sum1 <- number1 + number2 number3 <- 输入 sum2 <- sum1 + number3 计算算法中的计算步骤数
回答 7
回答
number2 <- 输入 number3 <- 输入 sum <- number1 + number2 + number3
|