06 算法基础：算法的定义、表现形式（自然语言、伪代码、流程图）、五个特性（有穷性、确定性、可行性、输入、输出）、好算法的设计目标

目录

1 算法的定义

2 算法的三种表现形式

2.1 自然语言

2.2 伪代码

2.3 流程图

3 算法的五个特性

3.1 有穷性

3.2 确定性

3.3 可行性

3.4 输入

3.5 输出

4 好算法的设计目标

4.1 正确性

4.2 可读性

4.3 健壮性

4.4 通用性

4.5 高效率与低存储量

---

1 算法的定义

        算法是指为解决特定问题而设计的一系列明确、有限的指令集合。简而言之，算法就是解决问题的方法或步骤。

---

2 算法的三种表现形式

2.1 自然语言

        使用日常使用的语言来描述算法的步骤，通常较为直观但可能缺乏精确度。

        示例：冒泡排序算法

从数组的第一个元素开始，比较相邻的两个元素。
如果前一个元素大于后一个元素，则交换它们的位置。
继续比较下一个相邻的两个元素，直到数组的最后一个元素。
重复上述过程，每次遍历都将最大的未排序元素移动到数组的末尾。
当没有更多的元素需要交换时，排序完成。

2.2 伪代码

        一种介于自然语言和编程语言之间的表达方式，用于描述算法的逻辑结构。

        示例：冒泡排序算法

procedure bubbleSort(list : array of items)n = length(list)for i from 0 to n-1swapped = falsefor j from 0 to n-1-iif list[j] > list[j+1]swap(list[j], list[j+1])swapped = trueif not swappedbreakend procedure

2.3 流程图

        采用图形化的方式展示算法的流程，适合表达分支、循环等控制结构。

---

3 算法的五个特性

3.1 有穷性

        有穷性是指算法应该在执行有限数量的步骤后终止。这意味着算法不应该包含导致无限循环或无限递归的逻辑。每当运行一个算法时，它最终应该给出一个结果并停止，而不是持续运行而没有终点。注意，算法在设计上是有穷的，但程序在实际执行过程中可能会无限期地运行。有穷性保证了算法的实用性和效率。

3.2 确定性

        确定性要求算法中的每一个步骤都必须是明确无误的，不允许有任何歧义。这意味着给定相同的输入，算法应当总是产生相同的结果，并且每一步都应该能够被精确地理解和执行。这确保了算法的可预测性和可靠性。

3.3 可行性

        可行性指的是算法中描述的操作都是基本的，可以通过已经实现的方法来完成。换句话说，算法中的每一步都应该是可以通过已有的技术手段实际执行的。这不仅仅涉及到计算资源的限制，还涉及到现有技术是否支持算法中提出的操作。可行性确保了算法不仅是理论上的可能，而且是实践上可行的解决方案。

3.4 输入

        输入是指算法开始执行前需要从外部接收的信息。这些信息可以是一个或多个量，也可以完全没有（即算法不需要任何外部输入）。输入为算法提供了处理的对象或条件，使得算法能够针对不同的情况产生相应的结果。正确识别和定义算法所需的输入是设计有效算法的关键部分之一。

3.5 输出

        输出是指算法执行完成后产生的结果。一个算法至少应该产生一个输出，这个输出是对输入数据进行处理后的结果，或者是对某个问题的解答。输出是衡量算法性能和效果的重要标准，也是算法与外界交流的主要方式。确保算法能够产生正确的输出是算法设计的核心目标之一。

---

4 好算法的设计目标

4.1 正确性

        正确性是算法设计中最重要且基本的要求。一个正确的算法应该能够准确地解决它所设计的问题。正确性可以细分为以下几个层次：

• 无语法错误：算法实现时不应包含任何语法错误，确保程序能够成功编译和运行。
• 对测试数据有效：算法应对常用的测试数据集产生正确的输出，满足预期结果。
• 对苛刻输入有效：对于经过精心设计的、复杂或极端的输入数据，算法也应能够产生正确的输出。
• 对所有合法输入有效：无论输入数据如何变化，只要符合输入规范，算法都应能够正确处理并给出满足要求的结果。

4.2 可读性

        可读性强调算法的易读性和易理解性。一个具有良好可读性的算法更容易被人阅读、理解和维护，有利于团队协作和技术传承。

• 简洁明了：算法描述应尽量简洁，避免不必要的复杂性。
• 结构清晰：合理组织算法结构，如使用恰当的注释、变量命名和模块划分，提高代码的可读性。

4.3 健壮性

        健壮性指的是算法在面对异常或非法输入时的表现。一个健壮的算法应能够有效地处理错误输入，防止系统崩溃或产生不可预测的结果。

• 错误检测：算法应具备检测输入数据合法性的能力，及时发现并处理错误。
• 异常处理：对于无法处理的错误输入，算法应提供合理的错误提示或采取安全措施，避免系统故障。

4.4 通用性

        通用性意味着算法应具有广泛的适用性，能够处理各种类型的数据集，而不仅仅是特定的案例。

• 适应性强：算法应能够在不同场景下灵活应用，不受特定数据格式或类型的限制。
• 扩展性好：算法设计时应考虑未来可能的变化，便于扩展和改进。

4.5 高效率与低存储量

        效率和存储量是评价算法性能的重要指标。高效的算法能够在较短的时间内完成任务，同时占用较少的存储资源。

• 时间效率：算法的执行时间应尽可能短，尤其是在处理大规模数据时。
• 空间效率：算法在运行过程中应尽量减少对内存的占用，降低存储需求。