多变量 Big-O 时间复杂度的简化
我正在尝试计算一个函数的时间复杂度，该函数使用合并排序对两个数组进行排序，找到它们的交集并对这个交集的结果进行排序。
通过分析所涉及的步骤，我发现关键步骤的时间复杂度为
O(a log a) + O(b log b) + O(a + b) + O((a+b)log(a +b))
其中 a 是第一个数组的大小，b 是第二个数组的大小
我将其进一步简化为： O(a log a) + O(b log b) + O((a+b)log(a+b))
这就是我陷入困境的地方。但根据我所读到的内容，a + b 大于 a 和 b 的想法允许我删除术语 a log a 和 b log b。使用这个，我得到了整体的大 O 表示法 O((a+b)log(a+b))。
我不确定这是否完全正确。
I am attempting to calculate the Time Complexity of a function that sorts two arrays using Merge sort, finds their intersection and sorts the result from this intersection.
By analyzing the steps involved, I found the key steps to have time complexities of
O(a log a) + O(b log b) + O(a + b) + O((a+b)log(a+b))
where a is the size of the first array and b is the size of the second array
I further simplified this down to:O(a log a) + O(b log b) + O((a+b)log(a+b))
This is where I got stuck. But from what I have read, the idea of a + b being greater than both a and b allow me to remove the terms a log a and b log b. Using this, I got the overall Big O Notation as O((a+b)log(a+b)).
I am not sure if this is entirely correct though.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你的分析是正确的。如果您不确定，让我一步一步更明确地解释它。
总体时间复杂度为：
O(alog(a)) + O(blog(b)) + O(alog(a+b) + blog(a+b))。对数是
x > 上的严格递增函数。 0，即log(x)> log(y) iff 当且仅当 x > y＞ 0 。
，因此输入大小不能为负，因此我们可以利用这一事实进行分析。
使用这个属性，我们知道 log(a+b) > log(a)
alog(a+b) > alog(a)。我们可以得出结论，
O(a log(a))是O(a log(a+b))的子集，因为 >当输入大小趋于无穷大时，每个算法的上限都是alog(a)，上限也是a log(a+b)。因此我们可以摆脱
O(a log(a))。对
O(b log(b)) 应用相同的逻辑。
最后，我们有
O(alog(a+b) + blog(a+b))，它对应于O((a+b)log(a+ b））。Your analysis is correct. Let me explain it more explicitly step by step if you are not sure about it.
Overall time complexity is:
O(alog(a)) + O(blog(b)) + O(alog(a+b) + blog(a+b)).Logarithm is a strictly increasing function on
x > 0, that is,log(x) > log(y)iffx > y > 0.Input size cannot be negative, therefore for our analysis we can use this fact.
Using this property, we know that
log(a+b) > log(a), thereforealog(a+b) > alog(a).We can conclude that
O(a log(a))is a subset ofO(a log(a+b))since every algorithm upper-bounded byalog(a)as input size goes to infinity is also upper-bounded bya log(a+b).Therefore we can get rid of
O(a log(a)).Apply the same logic for
O(b log(b)).At the end, we have
O(alog(a+b) + blog(a+b)), which corresponds toO((a+b)log(a+b)).