为什么数组插入的时间复杂度是O（n）而不是O（n + 1）？
我刚刚开始学习数据结构，并且在进行数组插入时想知道为什么数组插入的时间复杂度为O（n）而不是O（n + 1）？
在最佳情况下，当插入在最后时，时间复杂度为O（1）。我想我们正在考虑1插入元素，因为这里没有元素被移动。在最坏的情况下，假设我们必须移动n个元素然后插入新元素，那么时间时间复杂度是否应该为O（n + 1）？n用于移动元素，1用于插入。
非常感谢您的帮助。
问题答案：
O（n）的任何函数也是O（n + 1），反之亦然。低阶术语本质上会被忽略，因此+1不会产生任何有意义的作用。
-
就像谷歌地图一样，给定一百万个经纬度坐标列表，你将如何打印距离给定位置最近的k个城市？ 我在一次面试中问了这个问题。面试官说这可以在O（n）中通过使用插入排序到k来完成，而不是对整个列表进行排序，即NlogN。我在网上找到了其他答案，大多数人都说NLogN...他[面试官]正确吗？
-
我在GeekforGeekshttps://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/中检查“到达终点的最小跳跃次数”问题。我对这里提到的时间复杂度感到困惑，它是O（n^n）。 如果我看到上面的代码块，minJumps（arr，I，h）递归调用是从I=l1调用的。所以在每个递归步骤中，l（
-
据说 LinkedList 删除和添加操作的复杂性为 在 的情况下，它是 大小为“M”的数组列表的计算:如果我想删除第N个位置的元素，那么我可以使用index一次直接转到第N个位置(我不必遍历到第N个索引)，然后我可以删除元素，直到此时复杂度为O(1)，然后我必须移动其余的元素(M-N次移动)，所以我的复杂度将是线性的，即O(M-N-1)。因此在最后删除或插入会给我最好的性能(如N ~ M ),而
-
Redis zrank。 返回存储在key处的排序集中成员的排名，分数从低到高排序。排名（或指数）是基于0的，这意味着得分最低的成员排名为0。 为什么复杂度是O（log（N））？成员按分数排序，但zank按成员查询。 我找到了一些可能是答案的东西。 A.zset由ziplist实现时 大小小于128 每个成员的大小小于64字节 所以，ziplist的大小很小，所以这不是我讨论的问题。 B.当zse
-
我试图为这段代码找出一个大O的紧密界限： 如果我们从内最循环开始，它将在最坏的情况下运行k=n^2次，占O（N^2）。如果语句每次j=m*i时都为真，其中m是一个任意常数。由于j从1运行到i^2，这将在m={1,2，...，i}时发生，这意味着它将在i次时为真，i最多可以是n，所以最坏的情况将是m={1,2，...，n}=n次。如果i=n，第二个循环应该有O（N^2）的最坏情况。外环具有O（N）的
-
查找p的伪码算法为： 假设我有一个int值的数组H[1到m]，其中“p”是峰值元素，如果： 基本上，如果H【p】大于或等于其相邻元素，则H【p】为峰值。 假设数组H在开始和结束时都大于1个元素，数组为H[0到m 1]，其中H[0]=H[m 1]=无穷大。因此，H[0]和H[m 1]是哨兵。然后是元素p，其中1≤ p≤ n、 是一个峰值，如果H【p-1】≤ H【p】≥ H【p 1】。 我认为渐近时间