如何用多个变量简化 Big O 代数
How to simplify Big O algebra with multiple variables
假设算法的最坏情况运行时间可以描述为：
T(n) = O(n) + O(r^2) + O(n-r)
n 是输入大小，r 是根据算法创建分区的索引。
这个等式可以进一步简化吗？如果变量都是 n 那么它将是 O(n^2) 但是当涉及 r 时可以应用相同的想法吗？
由于 O(n-r) 被 O(n) 抑制，您可以写 T(n) = O(n) + O(r^2)。另外，正如您所知 r 介于 0 和 n 之间，您可以写成 T(n) = O(n + r^2)。但是，确切的术语是 T(n,r) = O(n + r^2).
假设算法的最坏情况运行时间可以描述为：
T(n) = O(n) + O(r^2) + O(n-r)
n 是输入大小，r 是根据算法创建分区的索引。
这个等式可以进一步简化吗？如果变量都是 n 那么它将是 O(n^2) 但是当涉及 r 时可以应用相同的想法吗？
由于 O(n-r) 被 O(n) 抑制，您可以写 T(n) = O(n) + O(r^2)。另外，正如您所知 r 介于 0 和 n 之间，您可以写成 T(n) = O(n + r^2)。但是，确切的术语是 T(n,r) = O(n + r^2).