问题
数据结构课堂上抛出一个问题，下面一段算法，复杂度是_______？
i=1;
while(i<=n)
i=i*3;A. O(3n)
B. O(n)
C. O(n3)
D. O(log3n)
意外
连叫三位同学回答，列一例外选B，让我有些吃惊。看来这是老师的问题，大家的思维没有到位。
分析及解答
所谓复杂度，是要对关键运算的次数进行计数。关键运算的次数，与问题规模有关。在这里，就是要考察循环了。关键运算是乘法，我们看执行算法中，需要多少次乘法。而问题规模呢？显然，执行多少次循环，与n的初值有关。这里设循环执行的次数为T(n)。
这里循环次数首先可以确定不是B所指定的线性关系。为直观起见，我们设n足够大，用于控制循环的变量 i 的变化过程是：
1（初值，由i=1）
3（第1次循环：i=i*3）
9（第2次循环：i=i*3）
27（第3次循环：i=i*3）
81（第4次循环：i=i*3）
273（第5次循环：i=i*3）
819（第6次循环：i=i*3）
2457（第7次循环：i=i*3）
……
可以看到 i 的值就这样，按着指数级的速度，向着(i<=n)这个使循环结束的条件奔去。
我们已经设循环执行的次数为T(n)。可以发现，当3T(n)≤n时，循环继续，循环结束时，恰 3T(n)>n，容易得到 T(n)≈log3(n)，论及复杂度，我们常只考察量级，故有T(n)=O(log3n)。
后续的疑问
课堂中我讲了这个结论得出的过程，大多数同学接受了。个别同学还在继续思考（好习惯，就着热乎劲，有质疑，有思考，学习的优良品质！）。问得最多的问题是：当n=3(或某一个具体的数)时，循环的次数不等于log3n！
对此，暴露出同学们对复杂度的理解中，还有两点不到位：
1. 复杂度只作粗略的，在定性（量级）上的考察，而不是定量（精确的计数算式）的计算，多几次少几次，不要细究了。注意说复杂度是O(log3n)，而不是log3n。要深刻理解这儿运用的“大O”的目的。
2. 复杂度只在意定性，而不在定量，为此，在衡定量级时，只保留高阶部分，低阶部分统计统不管，高阶式子的系数统统去掉。例如，关键运算的执行频度计数为10000n3+200n2+1000，在“取量级”的大方针下，也是O(n3)。因为在 n 值取很大的这个前提下，200n2+1000再大，在n3 面前也别抬头；n3前的系数再大，也不是主要因素。这是复杂度分析中，我们在抓主要矛盾。
3. 学计算机，计数是个很重要很重要的问题，计数的理论，也是深不可测。精确的计数，感兴趣的同学可以关注，但在算法的复杂度分析上，适应“就到量级”的处理，这里也有大学问，这也是实用的处理。
拓展
（1）下面一段算法，复杂度是_______？
i=n;
while(i>1)
i=i/3;A. O(3n)
B. O(n)
C. O(n3)
D. O(log3n)
E. O(1)
（2）下面一段算法，复杂度是_______？
i=1;
while(i<=n)
i=i+3;A. O(n/3)
B. O(n)
C. O(3n)
D. O(log3n)
（3）下面一段算法，复杂度是_______？
i=1;
while(i<=n)
n=i*3;A. O(∝)
B. O(n)
C. O(3n)
D. O(log3n)
解析
（1）D。和原问题其实一样，照文章中的思路做一遍即可得到答案。若关键运算执行次数与问题规模n无关时，复杂度为E. O(1)，显然，这里 i 的初值是 n ，并非无关。
（2）B。最迷惑人的，是A。循环的次数，循环次数约是 n3，但是，系数13是要去掉的，选B。
（3）错题！这段代码若执行，是个死循环，终止于内存溢出，或者有些对溢出不处理的语言，就真的一直会不停地执行下去。从算法角度，由于违反了“有穷性”，这也根本称不上是“算法”了。
