多变量 Big-O 时间复杂度的简化
Simplification of Multi-variable Big-O Time Complexity
我正在尝试计算一个函数的时间复杂度，该函数使用合并排序对两个数组进行排序，找到它们的交集并根据该交集对结果进行排序。
通过分析涉及的步骤，我发现关键步骤的时间复杂度为
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)).
虽然我不确定这是否完全正确。
您的分析是正确的。如果您不确定，让我一步一步更明确地解释它。
整体时间复杂度为：O(alog(a)) + O(blog(b)) + O(alog(a+b) + blog(a+b))。
对数是 x > 0 上的 严格递增函数 ，即 log(x) > log(y) 当且仅当 x > y > 0。
输入大小不能为负数，因此对于我们的分析，我们可以使用这个事实。
使用这个 属性，我们知道 log(a+b) > log(a)，因此 alog(a+b) > alog(a)。
我们可以得出结论，O(a log(a)) 是 O(a log(a+b)) 的 子集 ，因为 every 算法 upper-bounded by alog(a) 随着输入大小趋于无穷大也是 upper-bounded 乘以 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))。
我正在尝试计算一个函数的时间复杂度，该函数使用合并排序对两个数组进行排序，找到它们的交集并根据该交集对结果进行排序。
通过分析涉及的步骤，我发现关键步骤的时间复杂度为
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)).
虽然我不确定这是否完全正确。
您的分析是正确的。如果您不确定，让我一步一步更明确地解释它。
整体时间复杂度为：O(alog(a)) + O(blog(b)) + O(alog(a+b) + blog(a+b))。
对数是 x > 0 上的 严格递增函数 ，即 log(x) > log(y) 当且仅当 x > y > 0。
输入大小不能为负数，因此对于我们的分析，我们可以使用这个事实。
使用这个 属性，我们知道 log(a+b) > log(a)，因此 alog(a+b) > alog(a)。
我们可以得出结论，O(a log(a)) 是 O(a log(a+b)) 的 子集 ，因为 every 算法 upper-bounded by alog(a) 随着输入大小趋于无穷大也是 upper-bounded 乘以 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))。