4

我正在为一个主要是关于时间复杂度的考试而学习。我在解决这四个问题时遇到了一个问题。

1) 如果我们证明一个算法的时间复杂度为 theta(n^2)，是否有可能他需要为所有输入计算 O(n) 的时间？

2) 如果我们证明一个算法的时间复杂度为 theta(n^2)，是否有可能对某些输入进行 O(n) 的时间计算？

3) 如果我们证明一个算法的时间复杂度为 O(n^2)，是否有可能对某些输入进行 O(n) 的时间计算？

4) 如果我们证明一个算法的时间复杂度为 O(n^2)，是否有可能他需要为所有输入计算 O(n) 的时间？

谁能告诉我如何回答这些问题。当他们要求“全部”或“某些”输入时，我大多感到困惑。谢谢

4

2 回答 2

3

gkovacs90 答案提供了一个很好的链接：WIKI

  • T(n) = O(n3)，意味着 T(n)渐近增长不比 n3 快。一个常数k>0存在并且对于所有人n>N , T(n) < k*n3
  • T(n) = Θ(n3)，意味着 T(n)以与 n3 一样快的速度渐近增长。k1, k2 >0存在两个常数n>N , k1*n3 < T(n) < k2*n3

因此，如果T(n) = n3 + 2*n + 3

ThenT(n) = Θ(n3)更合适，T(n) = O(n3)因为我们有更多关于 T(n) 渐近行为方式的信息。

T(n) = Θ(n3)意味着对于 n>N，T(n) 的曲线将“接近”并“靠近” 的曲线k*n3, with k>0。 T(n) = O(n3)意味着对于 n>N，T(n) 的曲线将始终低于 的曲线k*n3, with k>0。

  • 1：没有
  • 2：是的，正如 gkovacs90 所说，对于较小的值，n您可以进行 O(n) 时间计算，但对于足够大的输入，我会说否。符号 Theta 和 Big-O 只表示渐近的东西
  • 3：是的
  • 4：是的

数字 4 的示例（愚蠢但仍然正确）：对于 Array A：Int[] 计算值的总和。你的算法肯定是：

Given A an Int Array

sum=0 
for int a in A
    sum = sum + a
end for
return sum

如果 n 是数组 A 的长度： 时间复杂度是T(n) = n。因此T(n) = O(n2)，由于 T(n) 不会比 n2 增长得快。我们仍然对所有数组进行 O(n) 的时间计算。

如果你发现这样的结果为时间（或内存）复杂度。然后你可以（当然你必须）改进你的函数的 Big-O / Theta（显然我们有：Θ（n））

最后几点：

  • T(n)=Θ(g(n)) 意味着 T(n)=O(g(n))。
  • 在计算复杂性理论中，有时会针对最佳、最差和平均情况计算复杂度。
于 2013-06-11T09:05:23.270 回答
1

“赤脚”的解释：

大 O 表示法用于设置上限。根据定义，总有一个索引（或输入长度），表示法是正确的。所以低于这个指数，任何事情都可能发生。

例如O(n^2)，用一个元素对数组（）进行排序比将元素写入输出（O(n)）所花费的时间更少。（我们不排序，我们知道它的顺序是正确的，所以它需要 0 时间）。

所以答案：

  • 1：没有
  • 2：是的
  • 3：是的
  • 4：是的

您可以在WIKI上找到详细易懂的描述

在这里你可以找到一个更简单的解释。

于 2013-06-11T07:48:44.500 回答