一个简单的求时间复杂度的题目
可能对与一个双重循环的这个样一个问题,我就不会再这里发帖了。例子如下:for(i = 0; i < n; i++)
for(j = 0; j < i; j++)
{ a++; }
基本语句c1:a++;
这个题目用数学归纳法很好证明:
当i = 0; f(n) = 0;
当i = 1; f(n) = 1;
当i = 2; f(n) = 2;
....
当i = n-1; f(n) = n-1;
基本语句执行的次数便是:0 + 1 + 2 + ....+ (n-1) = n(n-1)/2;
f(n) = n*(n-1)/2 < n*n/2 = O(n~2);
但是对与一个一个三重循环
for(i = 0; i < n; i++)
for(j = 0; j < i; j++)
for(k = 0; k < j; k++
{ a++; }
却不知道怎么分析,希望高手讲解!