在指定位置插入数组链表和对象时,大致分为两部分。
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过大或有其他因素时)。
注:上述讨论在一个前提下进行,在指定位置插入对象! 在指定位置插入对象! 在指定位置插入对象!
(不是按值搜索插入对象的位置。)