有这么一个少于十行的代码，你知道它的时间复杂度是多少吗？ 
 [图片] 


 a. T(n) \in \Theta(n^2) 


 b. T(n) \in \Theta(n) 


 c. T(n) \in \Theta(log n) 


投票

不管三七二十一，直接随便猜一个。我猜这个的时间复杂度是  \Theta(n^2) 因为有两个for循环，大家都知道有两个for循环那么时间复杂度也一定是  \Theta(n^2) 对不对。 
很可惜，还真不是 \Theta(n^2)， 而是 \Theta(n) 
为什么呢？且听我慢慢道来。 

在外部循环，有一个 i=2*，也就是每一次运行都会增长*2次，一直到n为止。而在内部循环，是根据外部循环来决定次数的，也就是说，外部运行多少次，内部就会运行多少次。 
既然是这样的结果，那为什么不是  \Theta(n^2) 呢？而是 \Theta(...