快速排序时间复杂性

Question

我最近读到了时间复杂度,我发现Quick sort的平均时间复杂度为O(nlog(n)).

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

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

Answer 1

如何logn进入复杂性公式？

• 对于每个步骤,您将在第一个和第二个半部分递归调用算法.

• 于是-所需的总步数,为的时候,它会从到达到多少n来1,如果你通过2每一步devide问题.
  所以你实际上正在寻找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符号使我们易于计算 - 平台无关近似算法将如何渐近地(在无穷远处)表现,这可以将算法的"族"划分为其复杂性的子集,并让我们在他们.

此外,使用的其他符号是小o,theta和大/小欧米茄.