对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为?答案是O(1)和O(n)。为什么?

如题所述

顺序存储可以实现“随机存取”,因此访问结点的时间复杂度为O(1),而插入、删除结点由于涉及到大量移动元素,故其时间复杂度为O(n)。

用存储结点的物理位置来体现结点之间的逻辑关系的存储方法。在高级语言中,一块连续的存储空间通常可用一个数组来表示。因此,顺序存储通常用一个数据元素类型的数组来存储。最经典的顺序存储结构是顺序表,将线性结构的元素按序存放在一个数组中。

扩展资料

数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。数据的存储结构,也称为数据的物理结构,是数据的逻辑结构在计算机中的实现。

链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构,链式存储结构通常借助于程序设计语言中的指针类型来实现。数据的链式存储结构可用链接表来表示。

参考资料来源:百度百科-顺序存储

温馨提示:答案为网友推荐,仅供参考
相似回答