下面的伪代码的时间复杂度是多少？
下面的伪代码的时间复杂度是多少？
提问于 2016-08-27 02:25:42
XYZ(a, b, c, m, n){
For p = 1 to m do
For q=p to n do
c[p,q] = a[p,q] + b[p,q];}我认为它是n+ n-1 + n-2 +.....+(n-m+1)。但我不确定。是这个还是m*n？
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-08-27 02:53:38
让我们简化您的代码：
For p from 1 to m
For q from p to n
Do something假设Do something部分是在固定时间内完成的，那么决定代码时间复杂度的是两个循环。外部循环运行m次，而内部循环运行n-p，其中p从1到m。
如果为m >= n，则Do something部件重复n+(n-1)+...+1 = n*(n+1)/2 = n²/2 + n/2 = O(n²)次。
否则，如果为n > m，则重复n+(n-1)+...+(n-m+1) = (n*(n+1) - (n-m)*(n-m+1))/2 = 1/2 * (n² + n - n² + 2*n*m - n - m² + m) = O(2*n*m - m²) = O(n²)次。
在任何情况下，O(n²)都是一个正确的答案，但如果是n >> m，则更准确的答案是O(n*m)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39172603
复制相关文章
相似问题
腾讯云开发者
