面临价值减法时的算法复杂度
Algorithm complexity when faced with substraction in value
我有以下公式，我必须对其进行简化以获得算法的时间复杂度：(n^2-n)/3。有没有适用的规则可以让我进一步简化这个表达式到更多 "common" Θ(n^2) 或类似的东西（我假设这就是结果，可能是错误的） .
我简直不知道怎么处理这里的减法。通常，如果两个值相加，你只考虑最大的那个来分析算法的复杂度。在这种情况下我该怎么办？
由于 Θ 是 紧界 ，没有更好的简化方法，如果某些函数 f(n) 都在 Θ(h(n)) 中并且在 Θ(g(n)) 中它意味着 Θ(h(n)) = Θ(g(n))，因此对于您会发现的任何其他函数，在您的示例中 Θ(n^2) 的信息增益是 none。
在处理 n^k - n^m 的减法时，其中 k>m，在分析大 Θ 符号时，您可以简单地 "throw" n^m。
这是真的，因为：
n^k - n^m <= n^k
-> and thus it is in O(n^k)
另一方面：
对于每个 m,k 都有一些值 N 这样对于所有 n>N：0.5n^k >= n^m，因此：
n^k - n^m >= n^k - 0.5n^k = 0.5n^k for n > N
-> it is also in Omega(n^k)
由于我们找到了上限和下限，我们可以得出结论 n^k-n^m，当 k>m 在 Θ(n^k) 时。
（对于一般的 f(n),g(n) 可以做类似的证明，它们具有不同的 Θ-复杂度 类）。
我有以下公式，我必须对其进行简化以获得算法的时间复杂度：(n^2-n)/3。有没有适用的规则可以让我进一步简化这个表达式到更多 "common" Θ(n^2) 或类似的东西（我假设这就是结果，可能是错误的） .
我简直不知道怎么处理这里的减法。通常，如果两个值相加，你只考虑最大的那个来分析算法的复杂度。在这种情况下我该怎么办？
由于 Θ 是 紧界 ，没有更好的简化方法，如果某些函数 f(n) 都在 Θ(h(n)) 中并且在 Θ(g(n)) 中它意味着 Θ(h(n)) = Θ(g(n))，因此对于您会发现的任何其他函数，在您的示例中 Θ(n^2) 的信息增益是 none。
在处理 n^k - n^m 的减法时，其中 k>m，在分析大 Θ 符号时，您可以简单地 "throw" n^m。
这是真的，因为：
n^k - n^m <= n^k
-> and thus it is in O(n^k)
另一方面：
对于每个 m,k 都有一些值 N 这样对于所有 n>N：0.5n^k >= n^m，因此：
n^k - n^m >= n^k - 0.5n^k = 0.5n^k for n > N
-> it is also in Omega(n^k)
由于我们找到了上限和下限，我们可以得出结论 n^k-n^m，当 k>m 在 Θ(n^k) 时。
（对于一般的 f(n),g(n) 可以做类似的证明，它们具有不同的 Θ-复杂度 类）。