Ⅰ 两道JAVA题目,求大神解答
A、
循环执行n次,时间复杂度为O(n)。
B、
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
第一重循环每1次,第二重循环n次,第一重循环每共n次,所以这个循环总共n²次
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
这个循环总共执行1+2+...+n=(1+n)n/2次
总共循环n²+(1+n)n/2次,时间复杂度为O(n²)。
C、
for(int i=1;i<=n;i*=2)
for(int j=1;j<=n;j++)
第一重循环每1次,第二重循环n次,第一重循环每共log2n次,所以这个循环总共nlog2n次,时间复杂度为O(nlog2n)。
D、
for(int i=1;i<=n;i*=2)
for(int j=1;j<=i;j++)
这个循环总共执行1+2+...+log2n=(1+log2n)log2n/2次,时间复杂度为O(n)