Arm*_*han 2 arrays algorithm time-complexity data-structures
我刚开始学习数据结构,在进行数组插入时,我想知道为什么数组插入O(n)的时间复杂度而不是O(n + 1)？
在最好的情况下,当插入位于最后位置时,时间复杂度为O(1).我想我们正在考虑1插入元素,因为这里没有移动任何元素.在最坏的情况下,鉴于我们必须移动n个元素然后插入新元素,时间复杂度不应该是O(n + 1)吗？n用于移动元素,1用于插入.
非常感谢帮助.谢谢.
che*_*ner 8
任何O(n)函数也是O(n + 1),反之亦然.低阶项基本上被忽略,因此+1没有任何有意义的贡献.
归档时间：
9 年 前
查看次数：
1926 次
最近记录：