首页 > 编程知识 正文

数组比链表速度更快的是,数组优于链表的特点

时间:2023-05-06 00:29:18 阅读:31849 作者:4640

在指定位置插入数组链表和对象时,大致分为两部分。

1、找到插入元素的位置

2、进行插入操作

找到位置所需的时间插入所需的时间=在指定位置插入对象所需的总时间

由此,可以假设几个值。

找到与要插入元素的位置相关的变量。

要插入的位置是z

获取一个对象引用所需的时间m

与插入操作相关的变量:

移动一个对象所需的时间、数组和链表相同: x

数组和链表中的对象数为y

执行插入操作所需的总时间: t

对于数组:

搜索所需时间: m*1

移动元素所需的时间(插入所需的时间((y-z ) x )

执行插入操作所需的时间: m*1(y-z ) x=t

对于链表:

搜索所需时间: m*z

移动元素所需的时间(插入所需的时间) 2x

执行插入操作所需的时间: m*z 2x=t

在排列式-m(y-z ) x=t中,m单项式对t影响因素小,因此省略时,为(y-z ) x=t

链表公式-m*z 2x=t中,2x单项式对t的影响因素很小,省略后,为m*z=t

可以得到数组和链表执行插入操作所需时间相等时的表达式。

(y-z ) x=m*z

y/z=m/x 1

根据环境(系统、APP应用程序等),m/x的比例可能不同,y/z也可能不同

这里假设m/x=1,可以得到以下内容。

y/z=2; y/2=z;

也就是说,如果执行插入操作的位置是对象总数的二分之一,则两个容器插入元素所需的时间相同。

的位置在二分之一前时,排列所需时间多;

插入位置变为二分之一时,链表所需时间变多。

当然,实际上,根据计算机不同而不同(获取对象参照、移动对象等所需的时间不同),

数组链表执行插入操作所需的时间不固定。

也就是说,在某些实际情况下,可以执行插入操作的位置是3/4,但数组比链表需要更多的时间(如果x太大或有其他因素)。

可以执行插入操作的位置是1/4,但链表需要比数组更多的时间。 m过大或有其他因素时)。

注:上述讨论在一个前提下进行,在指定位置插入对象! 在指定位置插入对象! 在指定位置插入对象!

(不是按值搜索插入对象的位置。)

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。