正文

logn的算法（logn的算法复杂度）

发布时间：2023-04-08 15:17:44 稿源：创意岭阅读： 100

大家好！今天让创意岭的小编来大家介绍下关于logn的算法的问题，以下是小编对此问题的归纳整理，让我们一起来看看吧。

开始之前先推荐一个非常厉害的Ai人工智能工具，一键生成原创文章、方案、文案、工作计划、工作报告、论文、代码、作文、做题和对话答疑等等

只需要输入关键词，就能返回你想要的内容，越精准，写出的就越详细，有微信小程序端、在线网页版、PC客户端

官网：https://ai.de1919.com。

创意岭作为行业内优秀的企业，服务客户遍布全球各地，如需了解SEO相关业务请拨打电话175-8598-2043，或添加微信：1454722008

本文目录:

1、对数的运算法则
2、关于log的公式
3、几个数学证明题，关于log的计算，求解答，高分悬赏
4、c++请问O(nlogn), O(1)分别指什么我知道O(n)指线性

logn的算法（logn的算法复杂度）

一、对数的运算法则

［log(a)(x)表示a为底x的对数］

log(a)(x)＋log(a)(y)=log(a)(xy);log(a)(x)－log(a)(y)=log(a)(x/y)

log(a^m)(x^n)=(n/m)log(a)(x)

换底公式log(a)(x)=log(b)(x)/log(b)(a)

=lg(x)/lg(a)=ln(x)/ln(a)

二、关于log的公式

当a>0且a≠1时，M>0,N>0，那么：

（1）log(a)(MN)=log(a)(M)+log(a)(N);

（2）log(a)(M/N)=log(a)(M)-log(a)(N);

（3）log(a)(M^n)=nlog(a)(M) （n∈R）

(4)log(a^n)(M)=1/nlog(a)(M)(n∈R)

（5）换底公式：log(A)M=log(b)M/log(b)A (b>0且b≠1）　

(6)a^(log(b)n)=n^(log(b)a) 证明：设a=n^x则a^(log(b)n)=（n^x）^log(b)n=n^（x·log(b)n）=n^log(b)（n^x）=n^(log(b)a)

(7)对数恒等式：a^log（a)N=N; log（a）a^b=b 　

（8）由幂的对数的运算性质可得(推导公式)

1.log(a)M^(1/n)=(1/n)log(a)M , log(a)M^(-1/n)=(-1/n)log(a)M

2.log(a)M^(m/n)=(m/n)log(a)M , log(a)M^(-m/n)=(-m/n)log(a)M

3.log(a^n)M^n=log(a)M , log(a^n)M^m=(m/n)log(a)M

4.log(以 n次根号下的a 为底)(以 n次根号下的M 为真数)=log(a)M , log(以 n次根号下的a 为底)(以 m次根号下的M 为真数)=(n/m)log(a)M

5.log(a)b×log(b)c×log(c)a=1

三、几个数学证明题，关于log的计算，求解答，高分悬赏

你就记住一点，任何大于0的n 取了log之后，就再也无法和之前的自己n平起平坐，哪怕是n的delta次方，delta特别小。因为考虑从f(n) = n^a - logn 求导得f‘(n) = a*n^(a-1)-1/n = (a*n^a - 1)/n 所以当n很大很大的时候a*n^a 一定是大于1的，所以导函数大于0，函数递增到没有尽头，从而n^a 把 logn 远远甩在身后。

所以(a) 两边取log得到 logn平方 vs n*loglogn 有n的完胜，右赢

(b) klogn vs logn的k次方这个很显然k是0或是负，都是klogn负，logn的k次方正，没得比；

其次两边取log变成logk + loglogn vs k*loglogn 所以当k在0,1之间，左赢；k=1，打平；k>1 右赢

变成logn * logloglogn vs ... 总之右边有n，右边完胜。

(d) 还是stirling，n^n vs sqrt(2*pi*n)/exp(n) * n^n 这个sqrt(2*pi*n)/exp(n) 显然比1要小，左胜

四、c++请问O(nlogn), O(1)分别指什么我知道O(n)指线性

这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度，也用于表示空间复杂度。

O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

比如时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。

再比如时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。

再比如O(logn)，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

O(nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。