时间复杂度计算

Question

时间复杂度计算

algorithmmathtime-complexity

7

我正在做一些考试题，但在这个问题上卡住了。已知快速排序算法的时间复杂度为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
我再次在这里卡住了。

- Xandru Mifsud

1

实际上，快速排序是O(n^2)的，只是名称有些令人困惑。 - Pooya

1

@Pooya，考试题目中给出了时间复杂度，我无法控制。然而，给定的时间复杂度对于最佳情况或平均情况是正确的。你提到的时间复杂度O(n^2)是针对最坏情况的。 - Xandru Mifsud

1

我的意思是，如果在每个步骤中选择元素的中位数作为枢轴元素，你可以证明最坏情况下运行时间实际上是O(n*log(n))。例如，请参见https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting。你能说出确切的问题文本吗？这似乎与此相关。 - Pachelbel

1

我明白了 :) 这是多项选择题吗？ - Pachelbel

3

我认为对于这个问题，你的考试批改者几乎需要接受提供的每个解决方案，因为问题并不是很明确。只是在 Landau 符号中给出了最坏情况下的复杂度，甚至实际系数都不知道——实际复杂度可能是像 4nlog(n) - sqrt(2n) + 100000n 这样的东西... 所以你能做的就是“假设”实际复杂度实际上是 nlog(n) 函数（甚至是 nld(n)，这似乎更合理;-)） - Pachelbel

显示剩余8条评论

6个回答

5

如果不知道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分钟）。

- Amitoj

这很有帮助！但是没有给出输入大小，并且考官需要一个“大约的值”- 这是一个相当模糊的问题。 - Xandru Mifsud

5

提供的信息是不完整的。

证明如下：

假设算法复杂度为 O(nlogn)。这意味着所需时间 t = c*nlogn。

因此，我们有以下方程式：

4 = c*n*logn

t = c*(n2)*log(n2)，其中 t 是所需答案

n2 = 2*n2

变量数量为 4 (n、n2、t、c)

唯一方程式数量为 3

由于需要至少 4 个方程式来解决这 4 个变量，所提供的信息是不完整的。

- Anmol Singh Jaggi

确实是这样！很惊讶这个问题会出现在考试中。我可以问一下为什么要引入“c”吗？我们从未真正解决过这样的问题，我们只是解释了时间复杂度是什么以及它如何因算法而异。 - Xandru Mifsud

1

这是如何定义大O复杂度的。如果一个算法是O(f(n))，那么它意味着所花费的时间与f(n)成线性比例关系。您可以在此处了解更多信息。 - Anmol Singh Jaggi

只是一点小提示：（确切的！）复杂度不必是cnlog(n)。O(nlog(n))只是说存在c>0和n>0（可能非常大），使得实际复杂度t(n)<=cn*log(n)。甚至可能t(8)比t(4)小，只要最终满足上述条件即可。 - Pachelbel

感谢大家的热心帮助！ - Xandru Mifsud

2

这听起来像是一道非常糟糕的考试题，可能是由于缺乏对Big-O符号实际含义的深入理解而编写的。其中存在许多问题-很多已经在其他回答中得到了解决。

最大的问题是Big-O符号不直接与实际时间有任何关系。它丢弃了需要回答实际问题所需的大量信息。

其他答案已经指出该问题没有给出原始输入集合中有多少项，只知道第二个集合是第一个集合的两倍。这一信息对于回答问题至关重要。但是还有几件事情他们没有提到...

首先，Big-O忽略了算法开销。实际上算法使用的设置时间可能需要3.5分钟，而不管它收到多少输入，对于原始输入集，实际处理时间只有约30秒。这将严重影响计算任意数量输入所需的时间。

但是，就像那样的遗漏一样，Big-O更进了一步。

查看维基百科中的此引用：

“在典型用法中，通常不直接使用O符号的正式定义；相反，通过以下简化规则派生函数f的O符号：”

如果 f(x) 是几个项的总和，则保留增长率最大的项，而且所有其他项都被省略。

如果 f(x) 是多个因素的乘积，则省略任何常数（不依赖于 x 的乘积中的项）。

这意味着时间计算可能包括最终被丢弃的多个项。如果算法需要 c * (n + n * log(n)) 的时间完成，并且没有超额开销，那么它在Big-O符号中仍然是 O(nlogn)。

对于考试问题，唯一可能的答案是“大于4分钟”。除非我们获得更多信息，否则我们无法了解更多信息：

- 有多少超额开销？ - 每个操作的时间成本是多少？ - 我们在讨论多少项？ - 其他被省略的项是什么？

- Corey

没错，这个问题确实有些欠缺。不幸的是，这些考试是进入大学的必要条件，对于全国范围内的考试来说，标准相当低令人惊讶。感谢您抽出时间来回答。 - Xandru Mifsud

1

我很喜欢@Amitoj的推理，但我想泛化一下。

令n0为导致运行时间为4分钟的元素数量，n1 = 2 * n0。那么我们有：

c = 4 mins / (n0 * log n0)

我们正在努力寻找。

t = c * n1 * log n1
  = 4 mins / (n0 * log n0) * n1 * log n1
  = 4 mins * (n1 / n0) * (log n1 / log n0)

n1 / n0 总是等于 2。

当 n0 => 无穷大时，log n1 / log n0 的极限为 1。

因此，是的，随着 n0 变大，t 的极限为 4 分钟 * 2 = 8 分钟。

- Erick G. Hagstrom

1

除了 Anmol Singh Jaggi 的所有答案都是错误的。

首先很容易看出这些信息不足以得到一个答案。原因如下：

你所需要做的就是解一个方程。如果你的算法时间复杂度为O(n logn)，那么你第一个方程式就是：

其中n是您列表的大小。如果他们想要您找出完成两倍大小算法需要多长时间，基本上他们想要找到x:

基本上，您需要解决一个包含3个未知数的2元方程组。这个方程组可能没有答案（但不适用于我们的情况），也可能有无限多个答案。

现在你需要做出对c1的假设。如果c1 = 1，则

将 n 替换到第二个方程式中，你会得到：x = 13.5。因此是 13 分钟和半分钟。

但是需要说明的是，我们得到的答案是基于c1等于1的假设，如果你有其他常数因子，你将会得到另一个答案。

- Salvador Dali

挑战在于脑力计算...考试不允许使用任何形式的计算器...！计算n的值将会相当困难。 - Xandru Mifsud

@XandruMifsud 好的，如果你认为提供一个错误的值（完全错误的解决方案）是更好的选择，那么请使用你接受的解决方案。在考试中，只需说明您无法回答3个未知数的2个方程组即可。另一方面，在考试中不需要5位数字精度。很容易看出nlogn = 4的解在2.5和3之间（这可以在2分钟内完成）。因此，选择2.75作为中间值。计算5.5 log 5.5也不难。所以不需要任何计算器，您可以在脑海中完成这项任务。 - Salvador Dali

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- josliber · Accepted Answer

我认为这个问题需要注意的第一件事是，考虑到排序数字花费了4分钟的时间，n必须非常大。例如，我刚刚在我的电脑上使用快速排序对十亿个数字进行排序，只用了不到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分钟要高得多。