程序员社区

数组和链表插入效率比较

 

数组和链表将对象插入指定位置时,大致可以分为两个部分:

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

由于不同环境(不同的系统、应用等),m/x的比例不同,y/z也可能不同

 

这里就假设m/x = 1,可得:

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

就是说当执行插入操作的位置在对象总数的二分之一时,两种容器插入元素所需的时间相等。

插入的位置在二分之一前时,数组所需时间较多;

插入位置在二分之一后时,链表所需时间较多。

 

当然,实际情况是,由于不同的计算机之间存在差异(获取对象引用、移动对象等所需的时间不同),

数组和链表执行插入操作所需时间相等的点,并不固定。

就是说,由于实际情况不同,有可能执行插入操作的位置在3/4,但是数组所用时间比链表的多(如果x太大,或其他因素);

可能执行插入操作的位置在1/4,但是链表所用时间比数组的多(如果m太大,或其他因素)

 

注意:以上讨论是在一个前提下进行的,将对象插入指定位置!将对象插入指定位置!将对象插入指定位置!。

(不是按值查找要插入对象的位置然后进行插入)

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 数组和链表插入效率比较

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区