Open Zakariyya opened 4 years ago
int i = 1; while(i<n){ i = i * 2; }
说明在while循环里面,每次都将 i乘以 2,乘完之后,i距离n就越来越近了。假设循环x次之后,i就大于2了,此时这个循环就退出了,也就是说2的x次方等于n,那么x= log2 n 也就是说当循环 log2 n 次以后,这个代码就结束了。
因此这个代码的时间复杂度为 O(log2n) 。 O(log2n)的这个2时间上是根据代码变化的,i = i * 3,则是 O(log3n)
如果 N = a^x (a>0, a!=1),即a的x次方等于N (a>0, a!=1),那么数x叫做以a为底N的对数,记作 x = loga N 。其中
说明在while循环里面,每次都将 i乘以 2,乘完之后,i距离n就越来越近了。假设循环x次之后,i就大于2了,此时这个循环就退出了,也就是说2的x次方等于n,那么x= log2 n 也就是说当循环 log2 n 次以后,这个代码就结束了。
因此这个代码的时间复杂度为 O(log2n) 。 O(log2n)的这个2时间上是根据代码变化的,i = i * 3,则是 O(log3n)
如果 N = a^x (a>0, a!=1),即a的x次方等于N (a>0, a!=1),那么数x叫做以a为底N的对数,记作 x = loga N 。其中