问如何找出算法的最佳时间复杂度？

EN

你在问如何证明一个算法的时间复杂度的下限。这有时是相当简单的，例如，如果你试图生成一个指数数的东西，你不能做比指数时间更好的事情，或者如果你需要在一个未排序的列表中找到最大数，你必须检查所有的数字，所以最佳时间界限是线性的。然而，这有时是非常困难的。计算机科学中最重要的开放问题之一是P=NP猜想，如果有人能证明任何NP完全问题的下界，这个猜想就可以解决。在这种方法上投入了大量的时间和精力，但没有产生任何显著的结果。此外，尽可能低的大O并不一定意味着没有更快的算法具有更好的恒定因子。

在实践中，恒定因素确实很重要，所以他们可能会问您是否可以在实现中改进恒定因素。此外，在面试中试图证明一些事情，充其量也就是碰巧失败。如果你被要求进一步优化算法，通常是因为有一种更快的方法来解决问题，面试官通常会提出问题并给出提示，试图提示你找到那种解决方案。

关于某些证明技术，比较排序上的nlog(n)界限的证明是一个有趣的证明。证明的基本思想是有n个！列表的可能排列，在最坏的情况下，每次比较只能消除其中的一半。根据Sterling的近似，这变成了nlog(n)界限。话虽如此，这是一个复杂的主题，太广泛了，不能在这里直接讨论。