1

我最近阅读了有关时间复杂度的文章，发现快速排序的平均时间复杂度为O(nlog(n))。

问题 1：我不明白时间复杂度方程中的log(n)是如何出现的？

问题 2：为什么我们总是使用大 O符号来计算算法的时间复杂度？为什么我们不使用其他符号？

4

4 回答 4

11

是如何logn进入复杂度公式的？

  • 对于每一步，您在前半部分和后半部分递归地调用算法。

  • 因此 - 所需的步骤总数是n如果1您将问题每一步除以 2 所需要的次数。
    所以你实际上正在寻找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 符号？
它简单且独立于平台。
op（有时甚至是比较）的确切数量取决于平台。（如果指令集 A 比指令集 B 更丰富，它可能需要更多操作）。
它绝对不是唯一使用的方法。对于现实生活中的应用程序，准确的运行时间（以秒为单位）是非常重要的因素，并且经常被使用。

因此，简而言之 - 大 O 表示法使我们易于计算 - 算法将如何渐近（在无穷大处）表现的独立于平台的近似，它可以将算法的“家族”划分为其复杂性的子集，让我们轻松比较他们。

此外，使用的其他符号是small o、theta 和 big/small omega。

于 2012-08-15T06:02:41.733 回答
2

问题1.快速排序的最坏情况时间复杂度是O(n^2)，而平均情况复杂度是O(nlogn)。logn 因子取决于枢轴，算法如何选择它。

快速排序最坏情况时间复杂度发生在枢轴递归地产生两个区域，一个是大小为 1 的元素，另一个是大小为 (n-1) 的元素。而平均情况发生在枢轴选择两个区域时，两个区域的大小都为 n/2 .

所以产生的递归关系是T(n)=2T(n/2)+Θ(n)。

                  f(n)=Θ(n)     
                  h(n)=n^log2(2)=>n 
                  since f(n) = h(n) so
                  T(n)= f(n)logn =>n(logn).

（这里我们使用 Θ 表示法，因为快速排序的最坏情况复杂度（大 O）是 O(n^2)，这里我们计算的是平均情况复杂度。）

问题 2. 我们使用大 O 表示法，因为它给出了最坏情况时间复杂度的概念，即使参数趋于无穷大，它也会限制算法，这意味着算法至少会在这个时间复杂度下运行并且不能超过它。

而还有其他符号，如小 o、theta 和大/小 omega，它们经常使用，因为它们的应用有限。

于 2012-08-15T10:01:39.470 回答
1

请阅读Cormen 等人的算法简介。在第 3 章中，您将找到关于算法复杂性分析的一个很好的解释。你会发现大 O 并不是唯一使用的渐近符号。

于 2012-08-15T04:23:51.120 回答
1

尽管这更多是关于计算机科学的一般问题，但可以通过对该问题的评论更彻底地解释——

问题 1：log(n) 表示问题的扩展率比 O(n) 问题高一个因子 log(n)。小于 n*log(n) 的项（如 n）被省略，因为它们的缩放比最大项慢。

问题2：还有其他指标，O（大O）是问题扩展的最坏情况率。请参阅评论中的书籍链接以了解其他人是什么/意思，因为那里有更好的解释。

于 2012-08-15T04:25:53.203 回答