本文介绍了给定代码的时间复杂度的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
限时送ChatGPT账号..这段代码将 a[i,j]
与 a[j,i]
交换为 j > 的时间复杂度是多少?i
(转置给定矩阵):
What is the time complexity of this code which swap a[i,j]
with a[j,i]
for j > i
(transpose the given matrix):
for(i=1;i<=(n-1);i++)
{
for(j=(i+1);j<=n;j++)
{
T=a[i,j];
a[i,j]=a[j,i];
a[j,i]=T;
}
}
推荐答案
内循环做从 n 到 1 递减的工作,实际完成的工作(交换数字)是 O(1),所以:
The inner loop does decreasing work from n to 1, and the actual work being done (swapping numbers) is O(1), so:
n 次运算 + (n - 1) 次运算 + (n - 2) 次运算 + ... + 2 次运算 + 1 次运算 = sum(1, n) 运算 = (n * (n + 1))/2 =(n2 + n)/2 = O(n2)
n operations + (n - 1) operations + (n - 2) operations + ... + 2 operations + 1 operation = sum(1, n) operations = (n * (n + 1)) / 2 = (n2 + n) / 2 = O(n2)
这篇关于给定代码的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
更多推荐
[db:关键词]
发布评论