包含在两个输入数组上循环的解决方案:O(n+m)或O(n*m)
我被问到一个问题，我们正在寻找重复的社会安全号码，就像ssn中的数组a和数组B一样。我的第一个想法是迭代每个数组，在一个hashmap，存储每个ssn的计数。当然，所有计数超过1的键都是重复的。我的理解是，这将是一个O(n+m)操作，其中m和n是每个数组中的元素数。有人告诉我，就时间复杂度而言，这是“非常低效的”，时间复杂度实际上是O(n*m)。这怎么正确？
共有1个答案
首先，O(n+m)比O(n*m)快。O(n*m)的时间复杂度如下所示：
for x in [1..n]
for y in [1..m]
因此，术语“非常低效”根本不适用，除非O(n+m)引起额外空间的紧张。在这种情况下，你可以澄清什么是最重要的因素，时间复杂度或空间复杂度。
-
我可以使用什么样的算法将两个排序数组合并为一个排序数组，最坏情况下的时间复杂度为O（log（m n）），其中n，m是数组的长度？我对算法的经验很少，但我检查了merge-sort，似乎合并步骤的时间复杂度是O（n）。在O（log（n））中是否有不同的合并方法？ 编辑：我最初没有考虑过，但可能无法在O（log（n））中合并两个排序的数组？实际目标是找到两个排序数组的中值。有没有办法做到这一点而不合并
-
我试图为这段代码找出一个大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）的
-
我在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（
-
问题内容： 是否真的计算了PHP数组的所有元素，还是将此值缓存在某个地方并被获取？ 问题答案： 好吧，我们可以看看源代码： call ，这反过来又需要非递归数组，该数组是通过以下方式实现的： 所以你可以看到，它的。
-
问题内容： 我刚刚开始学习数据结构，并且在进行数组插入时想知道为什么数组插入的时间复杂度为O（n）而不是O（n + 1）？ 在最佳情况下，当插入在最后时，时间复杂度为O（1）。我想我们正在考虑1插入元素，因为这里没有元素被移动。在最坏的情况下，假设我们必须移动n个元素然后插入新元素，那么时间时间复杂度是否应该为O（n + 1）？n用于移动元素，1用于插入。 非常感谢您的帮助。 问题答案： O（n）