在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是

如题所述

举报该问题

第1个回答 2016-06-25

有序？那么每次插入到链表尾结点吗？那么每次插入都要从头扫到尾吗，然后1+2+3+m=O(m^2)这样吗

第2个回答 2016-06-25

O(n)，因为链表只能顺序访问本回答被网友采纳

相似回答

在一个具有n个结点的有序单链表中,插入一个新结点并仍然保持有序的算法...答：在一个具有n个结点的有序单链表中插入一个新结点，并使其仍然有序的时间复杂性为O（n）；因为单链表保存的信息只有表头如果要在特定位置插入一个节点，需要先从表头一路找到那个节点。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储...

在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间...答：因为单链表保存的信息只有表头如果要在特定位置插入一个节点需要先从表头一路找到那个节点。数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O( ),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断...

在具有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂...答：【答案】：C 本题考查数据结构基础知识。在具有n个结点的有序单链表中插入一个新结点时，插入操作本身仅需要修改两个指针，时间主要消耗在顺序地比对需插入的元素与表中元素的大小，从而确定其插入位置。若要插入的元素小于表中的最小元素，则插入该元素时与表中的一个元素进行比较，若要插入的元素大于...

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂...答：时间复杂度N呗要想使插入的元素后仍然有序最大的就是把所有节点都遍历下. 所以是N;

数据结构题目;在一个具有n个结点的有序单链表中手插入一个新结点并...答：则有新结点有n+1个空位可以插入，插入到第一个空位需要比较1次，第二个空位比较2次。。。第n个空位比较n次，第n+1个空位不需要比较 3)最后，假设每个空位插入的可能性相同，因此，时间复杂度为1/(n+1) * (1+2+...+n)=1/(n+1) * (n+1)n/2=n/2，记为O(n)...

对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间...答：o(1)，直接定位，时间复杂度为1。链表中的数据是以结点来表示的，每个结点的构成：元素（数据元素的映象） +指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间...答：在给定值为x的结点后插入一个新结点的时间复杂度为O（n）。链表中的数据是以结点来表示的，每个结点的构成：元素（数据元素的映象） +指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取...

大家正在搜

在一个具有n个节点的有序单链表一个具有n个节点的单链表在一个单链表中p所指结点在含有n个节点的单链表一个有序的单链表单链表是什么的链式存储表示在循环单链表p所指结点之后如果单链表带有头结点在循环双链表的p所指结点之后

在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序...

数据结构题目;在一个具有n个结点的有序单链表中手插入一个新结...

在有n个结点的有序单链表中插入一个新结点，链表仍然保持有序的...

在一个具有n个结点的有序单链表中，插入一个新结点并仍然保持有...

一个关于数据结构线性表的题

建立一个有n个元素的有序单链表的时间复杂度度为什么是O(n^...

编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链...

数据结构考试题