如果我知道n＆gt;该算法的时间复杂性是多少m？
我有以下算法，发现两个排序列表的共同点：
findIntersection(List1, List2) {
list intersection;
int i = 0;
int j = 0;
while i < size of List1 and j < size of List2 {
if List1[i] < List2[j] {
i++;
}
else if List1[i] > List2[j] {
j++;
}
else {
add List1[i] to intersection;
i++;
j++;
}
}
return intersection;
}
我认为时间复杂性是o（m+n），但是如果我知道List2的大小大于List1的大小？
我的结论是，这仍然是O（M+N），因为在最坏的情况下，这两个列表都没有共同的项目，该算法仍然必须访问这两个列表中的每个项目，而与它们的大小无关。例如，如果List1 = {10、20、100}和List2 = {5、15、25、35、45、55、55、65、75、85、95}。但是我在线阅读，在时间复杂性为o（m+n）的算法中，我们知道n＆gt; m，它变成o（n），所以现在我不确定我是正确的。
I have the following algorithm that finds the items in common of two sorted lists:
findIntersection(List1, List2) {
list intersection;
int i = 0;
int j = 0;
while i < size of List1 and j < size of List2 {
if List1[i] < List2[j] {
i++;
}
else if List1[i] > List2[j] {
j++;
}
else {
add List1[i] to intersection;
i++;
j++;
}
}
return intersection;
}
I think the time complexity is O(m+n), but what if I know that the size of List2 is greater than the size of List1?
My conclusion was that it would still be O(m+n) because in a worst case scenario where both lists have no items in common, the algorithm will still have to visit every single item in both lists, independent of their size. For example, if List1 = {10, 20, 100} and List2 = {5, 15, 25, 35, 45, 55, 65, 75, 85, 95}. But I read online that in algorithms where the time complexity is O(m+n), it we know that n>m, it becomes O(n), so now I am not sure I am correct.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您的思考是正确的，循环永远不会像 m＆gt一样运行 n 倍。 1 。而且总是说复杂性是 o（n + m）。但是请考虑一下：
如果您知道 n＆gt; m ，然后 n + m＆lt; n + n = 2n 。
因此，然后 o（n + m）= o（2n）= o（n）。
You're right in your thinking, the loop will never run only n times as long as m > 1. And it is always true to say that the complexity is O(n + m). But think about this:
If you know that n > m, then n + m < n + n = 2n.
So then O(n + m) = O(2n) = O(n).
它将是
o（x），x是n和m的任何一种。假设n＆gt; m在最坏的情况下，它将是o（m+（nm）），它仍然是o（o（nm）） 。It would be
O(x),xbeing whichever ofnandmis greater. Assumingn>m, in the worst-case scenario, it would beO(m+(n-m))which is stillO(n).