algorithm - 输入的时间复杂度和大小

Question

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

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

2)如果我们证明一个算法的时间复杂度是theta(n^2)，有没有可能他对SOME输入的计算时间是O(n)？

3)如果我们证明一个算法的时间复杂度是O(n^2)，有没有可能他对SOME输入的计算时间复杂度是O(n)？

4)如果我们证明一个算法的时间复杂度是O(n^2)，有没有可能他对ALL inputs计算O(n)的时间？

谁能告诉我怎么回答这样的问题。当他们要求“全部”或“部分”输入时，我很困惑。谢谢

Answer 1

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

然后T(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 的示例(愚蠢但仍然正确):对于数组 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))。
• 在计算复杂性理论中，有时会针对最佳、最差和平均情况计算复杂性。