算法运行时间估算常见O(log(n))
log:求对数
例:a^b=n
a为底数,b为n的对数
记作:logA(n)=b ->求N的对数
计算器验算:
计算器的log默认以10为底 输入 10,log = 1。
10^1=10
换底公式:
验算:2^3=8,求8的对数,log(8)/log(2)=3,计算器默认以10为底
for(int i = 2;i<N;i*=2)
这段代码 i 以 幂增长方式增加
for的循环次数就是N的对数值,log2(N)
设一次运行的时间为O(1),这段的运行时间是O(log2(N))
忽略底数的记法就是 O(log(N))