二、算法和算法评价（王道）
1、算法具有的五个特性
答案
1、算法具有的五个特性：
有穷性—有穷步+有穷时间
确定性：指令明确，对于相同的输入有相同的输出
可行性：操作可以用基本操作经过有限次实现
输入：0或多
输出：1或多
2、好算法目标：
正确性、可读性、健壮性、高效率和低存储需求
2、算法的时间效率指算法时间复杂度，即执行算法所需的计算工作量；
评价一个算法的优劣不仅要考虑算法的时间、空间复杂度，还需要考虑正确性，可读性，健壮性，高效率低存储需求
3、（混淆点）某算法的时间复杂度为 n2 ，表明该算法的执行时间与n2成正比
4、算法的空间复杂度为O(1)，表明执行该算法所需的辅助空间大小相比输入的数据规模来说是个常量
辅助空间大小的理解
空间是算法运行所需的全部存储量（包括输入数据本身占用的空间），辅助空间是除输入数据外额外临时使用的存储空间。
算法的辅助空间大小是指算法在运行过程中，除了存储输入数据本身所占用的空间外，额外临时占用的存储空间大小。它是衡量算法空间复杂度的重要指标之一。
核心要点
- 仅算 “额外空间”
- 不包括输入数据本身占用的空间，只算算法运行时临时创建的变量、数组、栈、队列等辅助结构的空间。
- 例如：对数组排序时，数组本身的空间不算辅助空间，但若算法需要创建临时数组（如归并排序），则临时数组的大小属于辅助空间。
- 常见场景举例
- 原地算法（辅助空间小）： 如冒泡排序、插入排序，仅使用少量临时变量（如交换元素时的临时变量），辅助空间复杂度为 O(1)。
- 非原地算法（辅助空间大）： 如归并排序，需要额外的临时数组存储合并结果，辅助空间复杂度为 O(n)（n 为输入数据规模）。
- 与空间复杂度的关系
- 算法的空间复杂度 = 输入数据空间 + 辅助空间。
- 实际分析中，若输入数据空间固定（如给定数组），常简化为分析辅助空间大小。
通俗理解
想象你要整理一本书的章节顺序：
- 输入数据空间：书本身的纸张和文字占用的空间。
- 辅助空间：你整理时额外使用的草稿纸、便签、临时书架等临时工具的空间。 辅助空间越小，说明算法越 “节省空间”。
总结
辅助空间大小反映了算法运行时的 “临时内存开销”，在内存受限的场景（如嵌入式系统）中，选择辅助空间小的算法更为关键。
本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
