对于以下代码段,提供逐行分析并构造函数T(n),该函数将该代码段的运行时间作为“ n”的函数。同时确定此代码段的big-O。
x = 10,000;
for (int i = 1; i <= n; i++) {
if ( x < i)
sum += foo( i );``
system.out.print(sum);
else
for (j = 1; j <= i; j++)
system.out.print( i );
system.out.println( );
}
foo (a) {
for (int i = 0; i < n; i++)
sum += a * i;
return sum;
}
x = 10,000;
1:总共花费1个固定的任意时间长度,使该O(1)
for (int i = 1; i <= n; i++) {
2:运行n次,所以时间现在是O(n),因为O(n)>> O(1)[其中>>表示比]大]
if ( x < i)
sum += foo( i );``
system.out.print(sum);
3:由于foo中的for循环,这些行以O(n)运行,因此由于是嵌套的,因此对于n> 10000,这里的时间为O(n ^ 2)
else
for (j = 1; j <= i; j++)
system.out.print( i );
system.out.println( );
}
4:这还将在循环中运行n次,因此O(n ^ 2)的时间为<10000
foo (a) {
for (int i = 0; i < n; i++)
sum += a * i;
return sum;
}
5:请参阅第3条评论
最终:由于对于n> 10000和n <10000,此函数在O(n ^ 2)中运行,因此该函数为O(n ^ 2)