数组的定义或者常见的操作比较简单,就不在描述了,说说下面这个
大”O”表示法

无序数组的插入耗时:常数

无序数组的插入是目前为止可以接触到的算法中唯一一个耗时与数组的大小无关的
定义这个耗时为常量K
即T = K;
实际使用中,这个数值可能受到软硬件的因素比较多,例如计算器的计算能力、运行速度、编译器的程序编译速度等等,可能需要多次
测量我们才可以得到当前环境下的这个常量数值。

线性查找:与数据项个数K成正比

线性查找中, 寻找特定项所需的比较次数平均为数据项总数的一半。设N为数据项总数,搜索时间应该是跟数据项的一半成正比,
即有下面的公式:
T = K*N/2
将1/2并入K值,得到:
T=KN
即线性查找的时间与数据项个数成正比。

二分查找: 与log(N)成正比

T = Klog2(N)
常量简化:
T = K
logN

不要常数

大”O”表示法忽略常数,只关注数据项个数这个变量

用大”O”表示法展示运行时间

算法 大O表示法运行时间
线性查找 O(N)
二分查找 O(logn)
无序数组的插入 O(1)
有序数组的插入 O(N)
无序数组的删除 O(N)
有序数组的删除 O(N)