本文介绍了为什么数组插入的时间复杂度是O(n)而不是O(n + 1)?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我刚刚开始学习数据结构,并且在进行数组插入时我想知道为什么数组插入的时间复杂度为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)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-03 18:28
查看更多