Question

x=0;for(i=1;i<n;i++)for(j=1;j<=n-1;j++)x++;

x=0;for(i=1;i<n;i++)for(j=1;j<=n-1;j++)x++;求算法的时间复杂度。详细过程

Answer 1

当 i=1时，x++执行n-2次；
当 i=2时，x++执行n-3次；
当 i=3时，x++执行n-4次；
。。。
当 i=n-2时，x++执行1次；
当 i=n-1时，x++执行0次；

所以x++的执行次数为1+2+...+(n-2) = (n-1)*(n-2)/2
故时间复杂度为O(n^2)