我们知道，对于某些时间复杂度为 让我们说T(n) = n^2 + n + 1的算法，我们可以删除不太重要的项并说它具有最坏的O(n^2)情况。
当我们在计算诸如T(n) = 2T(n/2) + n + log(n)之类的算法的时间复杂度时呢？我们可以放弃不太重要的术语，只说T(n) = 2T(n/2) + n = O(n log(n))吗？
在这种情况下，是的，您可以安全地丢弃主导(log n(项。通常，只要只需要渐近行为而不是确切的公式，就可以执行此操作。
当您应用主定理求解递归关系时，例如
T(n( = a T(n/b( + f(n(
渐近地，你不需要F(n(的精确公式，只需要渐近行为，因为这就是主定理的工作原理。
在您的示例中，a = 2，b = 2，因此临界指数为 c = 1。然后主定理告诉我们 T(n( 在 Θ(n log n( 中，因为 f(n( = n + log n，它在 Θ(nc( = Θ(n( 中。
使用 f(n(= n 我们会得出同样的结论，因为这也在 Θ(n( 中。应用定理只需要知道f(n(的渐近行为，因此在这种情况下，可以安全地丢弃不影响f(n(渐近行为的主导项。
首先，您需要了解T(n) = n^2 + n + 1是一个封闭形式表达式，简单来说，这意味着您可以为 n 注入一些值，您将获得整个表达式的值。
另一方面，T(n) = 2T(n/2) + n + log(n)是递归关系，这意味着该表达式是递归定义的，要获得闭合形式表达式，您必须解决递归关系。
现在回答你的问题，一般来说，当我们能清楚地看到最高阶项时，我们去掉低阶项和系数，T(n) = n^2 + n + 1它的 n^2。 但是在递归关系中没有这样的高阶项，因为它不是一个封闭的形式表达式。
但要注意的一件事是，递归关系的闭合形式表达式中的高阶项将是递归树深度乘以递归关系中的高阶项的结果，所以在你的情况下它会是depthOf(2T(n/2)) * n，这将导致类似logn*n的东西，所以你可以说就大 O 表示法而言，它的O(nlogn)。