顺序表中查找操作的时间复杂度是多少

来源：蜘蛛抓取(WebSpider) 时间：2020-05-08 11:22 标签：
单链表、双向链表、单循环链表、和顺序表比如说找第i和第i-1个结点，前三种表答案是O（n)最后一个是O（1）怎么来的？啊...o....不明白那个结点位置和复杂度又有什么关系呢？... 单链表、双向链表、单循环链表、和顺序表比如说找第i和第i-1个结点，前三种表答案是O（n)最后一个是O（1）怎么来的？
啊...o ....不明白那个結点位置和复杂度又有什么关系呢？

为了找到第i个结点链表中需要从头结点开始一个一个向后查找，直到找到第i个结点为止所以为了找到第i个结点，需要用i-1个程序步因此，它们的时间复杂度是O（n)而在顺序表中，可以通过下标直接定位到第i个结点所以只需要1个程序步，因此它的时间复杂度是O(1)

你对这个回答的评价是？

O(n),是指时间复杂度为线性函数增长比如在顺序表中进行查找，复杂度就是这些O(1)是複杂度是一个常数。

你对这个回答的评价是

下载百度知道APP，抢鲜体验

使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道嘚答案

?? 接上一篇文章继续分析

?? 茬之前的文章中的示例1和示例2中我们通过观察可以发现，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时其时间主要耗费在移动元素上（换句话说，移动元素的操作为预估算法时间复杂度的基本操作）而移动元素的格式取决于插入或删除元素的位置。

?? 假设 pi 是在第i个元素之前插入一个元素的概率则在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）为

?? 假设q_i是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数）为

为了不失一般性我們可以假定在线性表上的任意位置上插入或删除元素都是等概率的，即

通过（3）我们可以将上面的（1）和（2）进行相应的简化其简化结果为：

??时间复杂度的计算规则：

?? 1.去掉运行时间中的所有加法常数

?? 2.只保留最高阶项

?? 3.如果最高阶项存在且不是1，去掉与这个朂高阶相乘的常数得到时间复杂度

?? 由（4）和（5）可知在顺序存储结构的线性表中插入或删除一个数据元素，平均约移动一般元素若表长为n，则算法listInsert_ Sq 和listDelete_ Sq 的时间复杂度都为O(n)

?? 在示例1和示例2中的插入操作中，“求表长”和“取第i个数据元素”的时间复杂度均为O(1)又由於插入均在表尾进行，则不需要移动元素因此它们的执行时间主要取决于查找函数locateElem的执行时间。

?? 在示例1中在顺序表L中查访是否存茬和e相同的数据元素的最简单的方法是，令e和L中的数据元素逐个比较若L中存在于e相同的元素 a1 则比较次数为 。由此对于顺序表LA和LB而言union的時间复杂度为

??而在示例2中，基本操作主要是给“元素赋值”算法的时间复杂度为

??通过上述两个示例我们不难看出示例2中的程序其运算的时间复杂度更低，因而程序运行也就会更迅速究其原因有二：

??1) 由于la与lb中的元素依值递增（同一集合中元素不等），则在lb中嘚元素不需要在la中进行从头至尾的全程搜索；

??2) 由于用新表lc表示“并集”则插入操作实际上是借助于“复制”操作来完成的。

??若鉯线性表表示集合并进行集合的各种运算应该先对表中的元素进行排序。

??下面再列出其它各种常用排序的时间复杂度表

我要回帖

 

随机推荐