Big O和Big Omega表示法算法

Question

有一种基于比较的排序算法，运行时间为O(n*log(sqrt(N)。考虑到存在用于排序的Omega(n(log(N)下限，这怎么可能呢？

Answer 1

基本上，这个问题要求您证明O(n*log(n)) = O(n*log(√n))，这意味着您需要找到某个常数c>0，使得: O(n*log(n)) = O(c*n*log(√n))。记住log n= n^(1/2)和√(n^(1/2))= 1/2*log(n)。因此，现在我们有O(n*log(n)) = O(1/2*n*log(n))。由于渐近表示法忽略了常数乘数，因此我们可以将其重写为O(n*log(n)) = O(n*log(n))。瞧，证明这是可能的。

Answer 2

对于基于比较的排序算法，您可以绘制决策树。它是一棵二叉树，表示算法完成的比较，并且这棵树的每一片叶子都是给定集合中元素的排列。

有n个！可能的排列，其中n是集合的大小，并且其中只有一个表示排序的集合。通向每个叶的路径表示实现由叶表示的排列所必需的比较。

现在让h作为决策树的高度，l作为叶子的数量。输入集的每个可能的排列都必须在其中一个叶子中，因此n！<= l。高度为h的二叉树最多可以有2^h的叶子。因此我们得到n！<= l <= 2^h。对两边都应用对数，这样就得到了h >= (n！)和log(n!)是Omega(nlog(n))。

因为决策树的高度代表了到达叶子所需的比较次数，这证明了基于比较的排序算法的下限是nlog(n)。这是不能更快完成的。因此，要使此任务正确，剩下的唯一选择就是假设Omega(nlog(n)也是Omega(nlog(sqrt(N)。=> (sqrt(N))= log(n^(1/2)) = (1/2)log(n) log(sqrt(n)) = n((1/2)log(n)) = (1/2)nlog(n)。忽略const = 1/2 (因为我们对无约束复杂性感兴趣)，您可以得到复杂性方面的nlog(sqrt(n)) = nlog(n)。