Question

数据结构“时间复杂度”的题目

1.下面程序段的时间复杂度为（ ）。 for ( int i = 0; i < m; i++ )
for ( int j = 0; j < n; j++ )
a[i][j] = i*j;
A.O(m2) B. O(n2) C. O(m*n) D. O(m+n)

2.执行下面程序段时，执行S语句的次数为（ ）。
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= i; j++ )
S;
A.n2 B. n2/2 C. n(n+1) D.n(n+1)/2

3.下面算法的时间复杂度为（ ）。
int f ( unsigned int n ) {
if ( n ==0 || n == 1 ) return 1;
else return n*f(n-1);
}
A.O(1) B. O(n) C. O(n2) D. O(n!)

Answer 1

1.C 二重循环，复杂度就是O(mn)
2.D 这个是特殊一点的二重循环，次数为1+2+……+n=n(n+1)/2，即D
3.B 这个是递归，求n!，也就是n*(n-1)*……*1，递归n次，复杂度为O(n)
不懂可问望采纳！

追问

书上答案是BBD,我感觉第一道是错的，应该是O(mn)，
第三道我想问一下为什么不是选D

追答

那我不就全错QAQ……搞得我很不好意思= =
关键是我检查了下还是觉得我是对的
第一个肯定是C，第二个难道不是等差数列么……怎么会是B呢？
第三个应该是B吧，举个例子，f(3)=3*f(2)=3*2*f(1)=3*2*1，这不是递归了n次么？其实这跟直接写循环结构是一样的，这个还要用到系统栈……
我觉得我的答案是对的，应该是书本错了！

Answer 2

O表示法首先要弄清楚什么用它来代表的上限的渐近运行时间的算法函数g（N），O（G（N））代表了一组函数。 <br />介绍到算法书定义：O（G（N））= {F（N）：存在正整数c和n0，因此，对于所有的n> = n0时，0 <= F（N）<= CG（）} <br />看到上面也可以忽略不明白，你只需要知道在低阶项的渐近积极的作用，在确定上限和下限，可以忽略不计，因为当N大，他们相对来说并不重要，指数最高的项目上脚的一小部分已经超越了所有的低阶项。同样，常系数最高的项目可以忽略不计，例如，O（F（N）），F（N）= 2毫米+ BN + C <br />，B，C是常数，而> 0，如何寻求，根据上述需求，放下低阶项，而忽略<br /> F（N）= O（N 2）<br />所以您获得的常数项主题<br /> F（N）= O（N 3）<br /> O（G（N））= O（N 3）<br /> H（N）= O（N 1.5次方）</ > O（nlogn）= O（nlogn）<br />因此，建立一个公式是不正确的

Answer 3