时间复杂度计算

Question

我目前正在做一些考试题目,并且此时陷入困境.我得知Quicksort算法的时间复杂度为O(nlog(n)).对于特定输入大小,对列表进行排序的时间为4分钟.问题继续问在同一系统上对两倍大小的列表进行排序需要多长时间.

我已经排除了时间不是8分钟(输入大小的两倍=持续时间的两倍,非常非常错误的推理).

我做过一些工作:

工作A.

• 4 = nlog(n)
• 4 = log(n^n)
• 16 = n^n
• 我基本上陷入了困境.

工作B.

• X = 2nlog(2n) >> 2n 因为输入加倍
• X = 2n(1 + log(n))
• X = 2n + 2nlog(n) >> nlog(n)是4几分钟
• X = 2n + 2(4) = 2n + 8
• 我再次陷入困境.

Answer 1

我认为关于这个问题首先需要注意的是,考虑到需要4分钟对数字进行排序,它n必须非常大.例如,我只是使用quicksort在我的计算机上排序十亿个数字,它花了不到3分钟.因此n可能大约10亿(给出或采取一个数量级).

鉴于这n是巨大的,将c*n*lg(n)某个常量近似于此运行时可能是合理的c,因为运行时扩展的低阶项对于如此大的不太相关n.如果我们加倍n,我们得到以下运算符的乘数与原始运行时相比:

[Runtime(2n)] / [Runtime(n)]
[c * (2n) * lg(2n)] / [c * n * lg(n)]
2 * lg(2n) / lg(n)
2 * log_n(2n)
2 * (1 + log_n(2))

这里,lg()是任意基数下的对数,是对数log_n()基数n.

首先,由于我们假设n很大,一种可能的方法是近似log_n(2)为0,因此运行时乘数将近似为2,总运行时间将近似为8分钟.

或者,由于我们可能知道n在一个数量级内,另一种可能性是近似乘数可能的值n:

• 如果n= 1亿,那么我们将乘数近似为2.075,总运行时间为8.30分钟.
• 如果n= 10亿,那么我们将乘数近似为2.067,总运行时间为8.27分钟.
• 如果n= 100亿,那么我们将乘数近似为2.060,总运行时间为8.24分钟.

请注意,我们的近似n产量的巨大变化在总运行时间的近似值中有相当小的变化.

值得一提的是,虽然这在纸面上看起来不错,但在实践建筑方面的考虑可能会导致现实生活中的运行时间是从我们这里计算的那些非常不同.例如,如果算法在将数据大小加倍后引发一堆分页,则运行时间可能远远高于我们在此处近似的约8分钟.

Answer 2

在不知道n的值的情况下,不可能计算绝对时间.
通过一些经验值来实现这一点.
假设'k'是一次操作所花费的时间

If, n = 2, k.n.log(n) = 4   => k.2.1 = 4   => k = 2
  if n is doubled, k.2n.log(2n) = 2.4.2 => 16 minutes

If, n = 4, k.n.log(n) = 4   => k.4.2 = 4   => k = 1/2
  if n is doubled, k.2n.log(2n) = 1/2.8.3 => 12 minutes

If, n = 64, k.n.log(n) = 4   => k.64.6 = 4   => k = 1/96
  if n is doubled, k.2n.log(2n) = 1/96.128.7 => 9.33 minutes

因此,当n增加时,所花费的时间接近两倍的时间(8分钟)

Answer 3

提供的信息不完整.

证明:

让算法复杂度O(nlogn).这意味着所花费的时间,t= c*nlogn.

因此,我们有以下等式:

• 4 = c*n*logn
• t = c*(n2)*log(n2),t所需答案 在哪里
• n2 = 2*n2

变量数= 4( ,n,n2,)t 独特方程总数= 3 由于我们需要至少在4个方程4级的变量,所提供的信息是不完整的.c