看这一道题如何求算法时间复杂度?(要详细一点)
看这一道题怎么求算法时间复杂度?(要详细一点)
看这一道题怎么求时间复杂度?
for(i=1;i<=n;i++) for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;
求时间复杂度O(n)
还有线性表那一块有这个符号&是什么意思?是取地址吗?啥时候加这个符号?
------解决方案--------------------
n^3
------解决方案--------------------
int ttt(int &ref)
{}
函数的传入参数就是引用:
对于函数来说,int ttt(int ref) 这就是传值,
ttt(3) 就是把3 赋值给 ref,然后函数内部使用,此传值不会带出返回。
对于int ccc(int &ref) 它引用的是传入值。
{
ref = 5;
}
int a = 0;
ccc( a )
cout<< a <<endl; 此时 a = 5;
------解决方案--------------------
这个从最里层循环开始计算:
最内层是 k=1-j
然后是 j=1-i
然后是 i=1-n;
这样有等式 T(N)为图片所示,然后就是数学计算了。 语句2 for (j=1;j<=i;j++)
语句3 for (k=1;k<=j;k++) x++;
第一次: 语句3 执行1次 因为语句2已经满足条件跳出循环(j=1;i=1)
第二次: 语句3执行1+2次 因为语句2 (j=1;i=2)
第三次: 语句3执行1+2+3次 。。。。。。。
第n次: 语句3执行1+2+3……+n ..........
所以T(n)=1+(1+2)+(1+2+3)……+(1+2+3……+n)
=n+2(n-1)+3(n-2)……+n(n-(n-1))
=n+2n+3n……+n*n -2-6- ……-n(n-1)
=n(n+1)*n/2-(1*1+2*2+3*3……+n*n-(1+n)n/2)
=n(n+1)*n/2-(n(n+1)(2n+1)/6-(1+n)n/2)
化简最后为
化开来就是
T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2
再根据大0法则,复杂度为N^3
看这一道题怎么求时间复杂度?
for(i=1;i<=n;i++) for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;
求时间复杂度O(n)
还有线性表那一块有这个符号&是什么意思?是取地址吗?啥时候加这个符号?
------解决方案--------------------
n^3
------解决方案--------------------
int ttt(int &ref)
{}
函数的传入参数就是引用:
对于函数来说,int ttt(int ref) 这就是传值,
ttt(3) 就是把3 赋值给 ref,然后函数内部使用,此传值不会带出返回。
对于int ccc(int &ref) 它引用的是传入值。
{
ref = 5;
}
int a = 0;
ccc( a )
cout<< a <<endl; 此时 a = 5;
------解决方案--------------------
这个从最里层循环开始计算:
最内层是 k=1-j
然后是 j=1-i
然后是 i=1-n;
这样有等式 T(N)为图片所示,然后就是数学计算了。 语句2 for (j=1;j<=i;j++)
语句3 for (k=1;k<=j;k++) x++;
第一次: 语句3 执行1次 因为语句2已经满足条件跳出循环(j=1;i=1)
第二次: 语句3执行1+2次 因为语句2 (j=1;i=2)
第三次: 语句3执行1+2+3次 。。。。。。。
第n次: 语句3执行1+2+3……+n ..........
所以T(n)=1+(1+2)+(1+2+3)……+(1+2+3……+n)
=n+2(n-1)+3(n-2)……+n(n-(n-1))
=n+2n+3n……+n*n -2-6- ……-n(n-1)
=n(n+1)*n/2-(1*1+2*2+3*3……+n*n-(1+n)n/2)
=n(n+1)*n/2-(n(n+1)(2n+1)/6-(1+n)n/2)
化简最后为
化开来就是
T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2
再根据大0法则,复杂度为N^3