c < log 2 n < n < ⟨ n log 2 n < n 2 < n 3 < 1 0 n c<\log _{2} n<n<\left\langle n \log _{2} n<n^{2}<n^{3}<10^{n}\right. c<log2n<n<⟨nlog2n<n2<n3<10n
设该算法共循环了x次,因为i被递归除即多次除以同一个数的逆过程相当于该数的指数形式,即用指数公式这个桥两头可以互通,即
2 x = N x = log 2 N \begin{aligned} 2^{x} &=N \\x &=\log _{2} N \\ \end{aligned} 2xx=N=log2N 循环中一共有两个操作,则其时间复杂度要乘2: O ( 2 ⋅ log 2 N ) = 2 ⋅ O ( log N ) = O ( log N ) \begin{aligned}O\left(2 \cdot \log _{2}^{N}\right) &=2 \cdot O(\log N) \\ &=O(\log N) \end{aligned} O(2⋅log2N)=2⋅O(logN)=O(logN) 用了两个变量所以空间复杂度为 O ( 2 ) = O ( 1 ) \begin{aligned} O(2)=O(1) \end{aligned} O(2)=O(1) constant常量复杂度
