DEV Community
·
静态数组 - 数据结构与算法笔记 📝
内容提要
本文介绍了静态数组的特点及基本操作，包括读取、插入和删除。静态数组大小固定，读取时间复杂度为O(1)，遍历为O(n)。删除操作分为末尾删除（O(1)）和中间删除（O(n)）；插入操作分为末尾插入（O(1)）和中间插入（O(n)）。
关键要点
-
静态数组的大小一旦声明后无法更改，满了后无法添加更多元素。
-
读取操作的时间复杂度为O(1)，即常数时间。
-
遍历操作的时间复杂度为O(n)，与数据大小线性相关。
-
末尾删除操作的时间复杂度为O(1)，通过软删除实现。
-
中间删除操作的时间复杂度为O(n)，需要将元素向左移动。
-
末尾插入操作的时间复杂度为O(1)，直接在长度索引插入。
-
中间插入操作的时间复杂度为O(n)，需要将元素向右移动以腾出空间。
-
总结了静态数组的基本操作及其时间复杂度。
延伸解读
静态数组的局限性
静态数组一旦声明，其大小便固定，无法动态扩展。这意味着在处理大量数据时，可能会遇到存储不足的问题，尤其是在需要频繁插入和删除操作的场景中。开发者需谨慎选择数据结构，以避免性能瓶颈。
时间复杂度的影响
静态数组的操作时间复杂度各不相同，读取操作为O(1)，而插入和删除操作在中间位置时为O(n)。这表明在设计算法时，选择合适的操作位置可以显著提高效率，尤其是在处理大规模数据时。
软删除的应用
在静态数组中，末尾删除操作可以通过软删除实现，时间复杂度为O(1)。这种方法适用于不需要立即清除数据的场景，但需注意，软删除可能导致数组中存在无效数据，影响后续操作的准确性。
延伸问答
静态数组的大小有什么特点？
静态数组的大小一旦声明后无法更改，满了后无法添加更多元素。
静态数组的读取操作时间复杂度是多少？
读取操作的时间复杂度为O(1)，即常数时间。
如何在静态数组中进行末尾插入？
末尾插入操作的时间复杂度为O(1)，直接在长度索引插入。
静态数组中间删除的时间复杂度是多少？
中间删除操作的时间复杂度为O(n)，需要将元素向左移动。
静态数组的遍历操作时间复杂度是什么？
遍历操作的时间复杂度为O(n)，与数据大小线性相关。
静态数组的删除操作有哪些类型？
删除操作分为末尾删除和中间删除，末尾删除时间复杂度为O(1)，中间删除时间复杂度为O(n)。
