Question

设n为正整数，利用大“O”表示法，将下列程序段的执行时间表示为n的函数：

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

Answer 1

x=1;
y=1;
for( i=0; i<n; i++) x++; O(n)

for(k=0; k<n; k++) O(n^2)
for(j=0; j<n; j++)
y++;

因此总体为O(n^2)