完成了数组的封装之后我们还需对其进行复杂度分析:
此处的复杂度分析主要是指时间复杂度分析,算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。
1.简单概念
** 2.大O简单定义(非数学领域)**
大O描述的是算法运行时间和输入数据之间的关系
3.简单程序时间复杂度分析
image.png
在上述中算法和n呈线性关系,那为什么要使用大O呢?称作O(n)?
其实上述的程序中,实际的实际时间复杂度:T = c1*n + c2,在这里忽略了常数c1和c2。
因此:算法和N呈线性相关,取n的高阶项,因为当n趋于无穷大的时候,低阶项起的作用很小。
4.对动态数组的时间复杂度进行分析
(1)动态数组添加操作时间复杂度分析
(1)
addLast(e)
方法 :只需在最后位置添加 时间复杂度 为O(1)
(2)
addFirst(e)
方法,数组中均需向后移动一位 时间复杂度 为O(n)
(3)
add(index,e)
方法,在index
位置插入e
,时间复杂度与选择的位置有关,选择最后时间复杂度 为O(1)
;选择第一个位置时间复杂度 为O(n)
;对于其他情况与概率有关,在平均情况下只需要移动n/2
个位置 时间复杂度 为O(n/2)=O(n)
总的来说:数组添加的时间复杂度为
O(n)
(最坏情况考虑)在添加的时候可能会触发
resize
方法,需要移动n个元素到新数组中 时间复杂度 为O(n)
image.png
(2)动态数组删除操作时间复杂度分析
相同的分析方法,可以得出删除操作的时间复杂度
image.png
(3)动态数组修改操作时间复杂度分析
对于修改,只要通过索引找到即可进行修改,时间复杂度为
O(1)
image.png
(4)动态数组查找操作时间复杂度分析
image.png
动态数组时间复杂度分析总结:
image.png
关于
resize
方法,我们完全使用最坏情况分析是不合理的,其分析情况我们将在下一节进行学习~
网友评论