渐近分析log n和log(n+m)中的时间复杂度
Time Complexity in asymptotic analysis log n and log (n+m)
受我 class.
中的对话启发的一些有趣的讨论
有两种算法，一种是时间复杂度log n，另一种是log(n+m).
我对平均情况的争论是否正确，log (n+m) 一个人会执行得更快，而他们在 运行 时间上没有差异，当渐近地考虑它时？因为取两者的极限和f1'/f2'会得到一个常数，所以它们的增长阶数是一样的
谢谢！
从问题中可以看出，n和m都是独立的变量。所以
当说
O(m + n) = O(n)
它应该适用于 任何 m，这不是：反例 是
m = exp(n)
O(log(m + n)) = O(log(n + exp(n))) = O(log(exp(n))) = O(n) > O(log(n))
这就是为什么在一般情况下我们只能说，
O(log(m + n)) >= O(log(n))
一个有趣的问题是何时 O(m + n) = O(n)。如果 m 增长 不快 那么 polynom 来自 n，即 O(m) <= O(P(n)):
O(log(m + n)) = O(log(P(n) + n)) = O(log(P(n))) = k * O(log(n)) = O(log(n))
在（多）图的情况下，我们很少有那么多边O(m) > P(n)：即使是完整的图Kn也只包含m = n * (n - 1) / 2 = P(n)条边, 这就是为什么
O(m + n) = O(n)
适用于普通图（没有parallel/multiple条边，没有环）
受我 class.
中的对话启发的一些有趣的讨论有两种算法，一种是时间复杂度log n，另一种是log(n+m).
我对平均情况的争论是否正确，log (n+m) 一个人会执行得更快，而他们在 运行 时间上没有差异，当渐近地考虑它时？因为取两者的极限和f1'/f2'会得到一个常数，所以它们的增长阶数是一样的
谢谢！
从问题中可以看出，n和m都是独立的变量。所以
当说
O(m + n) = O(n)
它应该适用于 任何 m，这不是：反例 是
m = exp(n)
O(log(m + n)) = O(log(n + exp(n))) = O(log(exp(n))) = O(n) > O(log(n))
这就是为什么在一般情况下我们只能说，
O(log(m + n)) >= O(log(n))
一个有趣的问题是何时 O(m + n) = O(n)。如果 m 增长 不快 那么 polynom 来自 n，即 O(m) <= O(P(n)):
O(log(m + n)) = O(log(P(n) + n)) = O(log(P(n))) = k * O(log(n)) = O(log(n))
在（多）图的情况下，我们很少有那么多边O(m) > P(n)：即使是完整的图Kn也只包含m = n * (n - 1) / 2 = P(n)条边, 这就是为什么
O(m + n) = O(n)
适用于普通图（没有parallel/multiple条边，没有环）