谢谢ayalicer，指数变对数我是知道的。我的疑惑在“2的f(n)次方”设i=i*2这句的频度是y。那为什么是2的y次方小于等于n呢？我知道当运行第一次判断,i=2,第二次i=4,第三次i=8，第四次i=16，对于n次循环来说。只执行了其中的一部分。当然复杂度小于n.但执行的这一部分为什么用2的y次方来表示，而不是n除以一个值，比如n/2呢？另外，当i=i*3，变成3的时候，复杂度是否就是O(log<3>N)呢？
-
月寒 回复于：2007-09-26
-
O(log<3>N)?对的
不过复杂度最后还是要转化成标准化形式
O(LogN)即可