问题描述
我刚刚开始学习数据结构,并且在进行数组插入时我想知道为什么数组插入的时间复杂度为O(n)而不是O(n + 1)吗?
I just started learning data structure and while going through array insertion I wondered why is time complexity of array insertion O(n) and not O(n+1) ?
在最佳情况下,在最后插入时,时间复杂度为O(1)。我想我们正在考虑1插入元素,因为这里没有元素被移动。
在最坏的情况下,假设我们必须移动n个元素然后插入新元素,那么时间复杂度是否应该为O(n + 1)?
n用于移动元素,而1则用于插入。
In best case, when insertion is at the last place,the time complexity is O(1). I suppose we are considering 1 to insert the element as no elements are moved here.In worst case, Given that we have to move n elements and then insert the new element, Shouldn't the time time complexity be O(n+1) ?n for moving the elements and 1 for insertion.
非常感谢帮助。谢谢。
推荐答案
任何一个O(n)函数也是O(n + 1),反之亦然。低阶字词实际上会被忽略,因此+1不会产生任何有意义的作用。
Any function that is O(n) is also O(n+1), and vice versa. Lower-order terms are essentially ignored, so the +1 doesn't contribute anything meaningful.
这篇关于为什么数组插入的时间复杂度是O(n)而不是O(n + 1)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!