线性表(a1,a2,…,an)以链表方式存储时,访问第i位置_

XaLo`g

时间复杂度指的是一个数量级的概念，i只是单纯的一个位置

在这里可以计算访问某一节点的平均时间，访问第一个时间为1，第二个时间为2、、、以此类推，访问第n个的时间为n，求得平均时间，(1+n)*n/2n，这个时间的数量级为O(n)

编辑于 2018-07-06 16:59:23 回复(1)

我的大学

C

元素在链表的位置为i意味通过遍历执行i次，则i<n，可以知道时间复杂度为O(n).

编辑于 2021-01-09 20:58:49 回复(6)

zfun

分清所花时间和时间复杂度

发表于 2018-06-03 21:37:14 回复(0)

我是初学者

一个算法的时间复杂度的定义是问题规模（即n）的函数，故不是0（i）。

发表于 2018-12-12 21:22:54 回复(0)

红莲天舞

C 链式存储访问元素要遍历

编辑于 2015-07-02 17:56:30 回复(0)

eeeegoist

线性表分为链表与顺序表（即数组），由于顺序表为随机存取，所以访问顺序表元素的时间复杂度为O(1)；由于链表访问需要逐个遍历，所以访问链表元素的时间复杂度为O(n)。

发表于 2023-10-21 11:41:00 回复(0)

pipi

写个O(是误导吗)

发表于 2015-04-03 16:20:36 回复(1)

惜平

文字游戏

发表于 2024-11-25 08:01:41 回复(0)

ssp到手了的修勾很卖萌

随着数组长度n的增大，计算复杂度也线性增大。故复杂度为O(n)。

发表于 2022-10-11 07:49:14 回复(0)

牛客279254448号

线性表的链式存储不是开辟的不是一片连续的地址空间，所以这里的ai不一定是在链表中排到第i位，此时应看成最坏的情况，时间复杂度为O（n）

发表于 2022-05-05 20:32:35 回复(0)

不负时光201811112314107

链式存储，不具备随机存取，需要从头顺序存取元素，所以o（n）

发表于 2022-03-02 12:03:33 回复(0)

AAS48

问的不是时间复杂性吗？

发表于 2021-12-13 15:36:50 回复(0)

萧瑶儿🐰

感觉问的不明确吧，若i是变动的，应该是o(n)，若是固定索引值，应该是o(i)

发表于 2021-05-24 07:48:56 回复(0)

友人说201904171536944

c

发表于 2019-04-30 19:32:35 回复(0)

hpjk07

链式访问需要遍历

发表于 2019-03-23 09:04:26 回复(0)

Eden0206

复杂度还是要用正经的复杂度度量方式比较好

发表于 2018-07-03 01:48:49 回复(0)

大将军豆腐脑好

***了，手误

发表于 2017-05-11 08:25:41 回复(0)

vcjmhg

i只是误导

发表于 2016-11-16 22:17:42 回复(0)

seaway

O(i)

编辑于 2016-03-10 20:36:35 回复(0)

gendlee

假如链式存储数组为a[n]，要查找的元素为k，则伪代码如下：
while((i<n)&&(a[i]!=k)i++; 或
for(i=0;(i<n)&&(a[i]!=k);i++)
随着数组长度n的增大，计算复杂度也线性增大。故复杂度为O(n)。

编辑于 2015-10-26 16:23:41 回复(0)

线性表(a1,a2,…,an)以链表方式存储时,访问第i位置

问题信息

热门推荐

相关试题