一.O(logn)代码小证明
我们先来看下面一段代码:
对数函数log正规写法，int cnt = 1;while (cnt < n){ cnt *= 2; //时间复杂度为O(1)的程序步骤序列}
由于cnt每次在乘以2之后都会更加逼近n，也就是说，在有x次后，cnt将会大于n从而跳出循环，所以$2 ^ x = n$，也就是$x = log_2n$，所以这个循环的复杂度为O(logn)
二.典型时间复杂度
$c$ 常数$logN$ 对数级$log ^ 2N$ 对数平方根$N$ 线性级$NlogN$$N ^ 2$ 平方级$N ^ 3$ 立方级$2 ^ N$ 指数级
log是对数的符号,你所举例应该是以10为底的对数,对数其实就是指数的逆运算,log后面的数字叫真数,真数在指数运算中是值,比如10^2=100,则log100=2,10^3=1000,则log1000=3,所以log2等于多少的意思就是10的多少次方等于。
由此我们可以得知，$logN$的算法效率是最高的
三.常见的$logN$算法
1.对分查找
2. 欧几里得算法
3.幂运算
- (long)Pow:(long)x n:(unsigned int)n{ if (n == 0) { return 1; } if (n == 1) { return x; }if ([self isEven:n]) { return [self Pow:x * x n:n / 2]; } else { return [self Pow:x * x n:n / 2] * x; }}- (BOOL)isEven:(unsigned int)n{ if (n % 2 == 0) { return YES; } else { return NO; }}
四.库里的log函数
在$$库里有log()函数和log2()函数
log()函数的底数默认为自然对数的底数e
log2()函数的底数很显然就是2咯qwq
include <cstdio>include <algorithm>define DEBUG(x) cerr << #x << "=" << x << endlint main(){ cout << log(M_E) << endl; cout << log2(2) << endl; return 0;}
1、a^log(a)(b)=b 2、log(a)(a)=1 3、log(a)(MN)=log(a)(M)+log(a)(N);4、log(a)(M÷N)=log(a)(M)-log(a)(N);5、log(a)(M^n)=nlog(a)(M)6、log(a)[M^（1/n）]=log(a)(M)/。
然后我们就会得到
的结果
情况一：计算底为10的log（10）即lg：一般的计算器都默认log的底数为10，因此计算这类对数时，直接点击计算机的“log”键，再打上数字即可。例如，求“lg（10）”可在科学计算器中按下：“log”，“10”，“=”即可。
$$库里有两个常量M_E和M_PI M_E代表的是自然对数的底数e M_PI代表的是圆周率π
最后，也是最基本的最重要的
当题目的数据范围达到了$10^{18}$的时候，很显然就要用O(logn)的算法或数据结构了
计算机上的log都是默认以10为底的对数，因此log100 = 2，log1000 = 3。如果需要计算以非10为底的对数，要使用换底公式，比如想计算以7为底12的对数，在计算器上的操作应该是 (log12) / (log7)
