<分区>
我最近阅读了有关时间复杂度的文章，发现快速排序的平均时间复杂度为 O(nlog(n))。
问题 1:我不明白的是 log(n) 是如何出现在时间复杂度方程中的？
问题2:为什么我们总是使用大O表示法来求算法的时间复杂度？为什么我们不使用其他符号？
<分区>
我最近阅读了有关时间复杂度的文章，发现快速排序的平均时间复杂度为 O(nlog(n))。
问题 1:我不明白的是 log(n) 是如何出现在时间复杂度方程中的？
问题2:为什么我们总是使用大O表示法来求算法的时间复杂度？为什么我们不使用其他符号？
最佳答案
logn 是如何进入复杂度公式的？
因此 - 如果将问题除以 2，所需的总步数就是从 n 到达 1 所需的次数每一步。
所以你实际上是在寻找这样的k:
n / 2 /2 / 2 / ... /2 = 1
^
(k times)
但是，请注意方程实际上是:n/2^k = 1。由于 2^logn = n，我们得到 k = logn。因此算法所需的步骤(迭代)数为 O(logn)，这将使算法 O(nlogn) - 因为每次迭代都是 O(n)。
注意:这里的复杂度并不精确，在极少数情况下快速排序会衰减到 O(n^2)，这取决于主元的选择。 “每步将问题除以 2”是一种简化，但它不会改变算法的平均分析。
为什么要使用大 O 表示法？
它简单且平台独立。
操作的确切数量(有时甚至是比较)取决于平台。 (如果指令集 A 比指令集 B 更丰富，它可能需要更多的操作)。
它绝对不是唯一使用的方法。对于现实生活中的应用程序，精确运行时间(以秒为单位)是非常重要的因素并且经常被使用。
所以，简而言之 - 大 O 符号让我们很容易计算 - 平台无关的近似算法将如何渐进(在无穷大)，它可以将算法的“家族”分成其复杂性的子集，让我们它们之间很容易比较。
此外，使用的其他符号是 small o, theta and big/small omega .
关于java - 快速排序时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11963986/