优化存储：数组与广义表的时间效率与特殊矩阵

本章节主要探讨了算法的时间代价，特别是针对第5章中的数组与广义表。在讲解这些概念时，首先定义了数组作为数据结构的基础，它是由相同类型的数据元素构成的有限序列，存储在连续的内存单元中，支持随机访问。数组的特点包括所有元素数据类型一致，通过下标计算元素位置，并可以将二维数组转换为一维思考，区分行主序和列主序存储。 在存储效率方面，提到了时间效率为O(a.n+a.t)，其中a代表某些固定的常数，n表示数组长度，t可能涉及特定操作的复杂度。这种效率分析强调了在某些情况下，通过牺牲空间来换取时间的优化策略。 接下来，章节介绍了特殊矩阵的压缩存储方法，对于对称矩阵，只需存储上三角或下三角部分的元素，这样可以大大节省空间，比如一个n阶对称矩阵只需存储n(n+1)/2个元素，比完全存储节约了一半空间。对于对称矩阵，可以通过索引sa[k]与其对角线以下的元素aij建立对应关系，如以"行优先顺序"存储。 此外，还提到了三角矩阵和稀疏矩阵，它们是特殊的矩阵类型，其中包含大量相同的元素或零元素，且分布有规律。这些特殊矩阵的存储方式旨在进一步优化空间利用，减少冗余存储，提高算法效率。 总结来说，这一章内容深入浅出地讲解了数组的定义、特性及其在时间效率上的考量，以及如何针对特殊矩阵的结构特点进行高效存储。这不仅有助于理解基本的数据结构，也为优化算法设计提供了实用的策略。对于数据结构的学习者和工程师来说，理解和掌握这些知识点至关重要。