algorithm - 如何用多个变量简化 Big O 代数

Question

假设算法的最坏情况运行时间可以描述为:

T(n) = O(n) + O(r^2) + O(n-r)

n 是输入大小，r 是根据算法创建分区的索引。

这个等式可以进一步简化吗？如果变量都是 n 那么它将是 O(n^2) 但是当涉及 r 时可以应用相同的想法吗？

Answer 1

由于 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)。