我正在为一个主要是关于时间复杂度的考试而学习。我在解决这四个问题时遇到了问题。
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)的时间?
谁能告诉我怎么回答这样的问题。当他们要求“全部”或“部分”输入时,我很困惑。 谢谢
最佳答案
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))。
- 在计算复杂性理论中,有时会针对最佳、最差和平均情况计算复杂性。
关于algorithm - 输入的时间复杂度和大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17038580/