[我们知道，对于某些时间复杂度为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))吗？
首先，您需要了解T(n) = n^2 + n + 1是一个封闭形式的表达式，简单来说，它意味着您可以为n注入一些值，您将获得整个表达式的值。
[另一方面，T(n) = 2T(n/2) + n + log(n)是recurrence relation，这意味着该表达式是递归定义的，要获得封闭形式的表达式，您将必须解决递归关系。
现在回答您的问题，一般来说，当我们可以清楚地看到最高阶项时，我们会在T(n) = n^2 + n + 1中的n ^ 2中删除低阶项和系数。但是在递归关系中，没有这样的最高阶项，因为它不是封闭形式的表达式。
但是要观察的一件事是，递归关系的闭合形式表达式中的最高阶项将是递归深度树的结果乘以递归关系中的最高阶项，因此在您的如果是depthOf(2T(n/2)) * n，则结果类似于logn*n，因此可以说用大O表示法表示为O(nlogn)。
在这种情况下，是的，您可以放心地放弃占主导地位的（log n）术语。通常，只要您只需要渐近行为而不是确切的公式，就可以执行此操作。
当您应用Master theorem来解决递归关系时>]
T（n）= a T（n / b）+ f（n）
渐近，那么您不需要f（n）的精确公式，只需渐近行为，因为这是Master定理的工作原理。
在您的示例中，a = 2，b = 2，因此临界指数为c =1。然后，主定理告诉我们T（n）在Θ（n log n）中，因为f（n）= n + log n，以Θ（n c
）=Θ（n）表示。我们将使用f（n）= n得出相同的结论，因为这也位于Θ（n）中。应用定理仅需要知道f（n）的渐近行为，因此在这种情况下
丢弃不影响f（n）渐近行为的支配项是安全的。