数学基础知识

算法里涉及到一些数学常识,比如计算时间复杂度的时候,遇到O(logN) O(log N) 代表是什么意思?

搞清楚后需要简单记录,避免后忘记相关知识。

数学常识——对数

logK log K , 指的是对数k,百度百科定义如下:

在数学中,对数是对求幂的逆运算,正如除法是乘法的逆运算,反之亦然。 这意味着一个数字的对数是必须产生另一个固定数字(基数)的指数。

如果a的x次方等于N(a>0,且a≠1),那么数x叫做以a为底N的对数(logarithm),记作x=logaN x=log_aN 。其中,a叫做对数的底数,N叫做真数。

简单用公式来描述: ax=Na^x=N, 如果为了得出x的值,可以用表达式 x=logaN x=\log_aN , a是对数的底数, N是真数, 通常我们定义当a=2的时候,忽略不写底数a,比如2x=N2^x=N,可以简写为 logNlog N

还有一些其他对数简写:

  • log以e为底,以x为真数, 可以写作:logex=lnx log_ex = ln x
  • log以10位底,以x为真数, log10x=lgx log_{10}x =lg x

logN log N 的曲线图如下:

logN

数学常识——常数e

e代表是数学常数e, 是自然对数的底数 自然对数是以e为底的对数函数,e是一个无理数,约等于2.718281828

更加简单的说,假如你有1块钱,银行抽风了一年利率100%,如果一年结算一次,

  • 一年后就能得到1×(1+1)=2块钱
  • 如果半年结算一次,上半年的计息计入下半年的本金,一年后就能得到1×(1+0.5)×(1+0.5)=1×(1+0.5)=2.25块钱。这样就多出了两毛五。
  • 如果像余额宝一样,每天都结算利息,那么一年后你就能得到 1(1+1/365)365=2.7145674550 1*(1+1/365)^365=2.7145674550
  • 比一年结算一次多了 七毛多
  • 那么,如果每一秒结算一次,或者每一毫秒结算一次,或者每过无穷短的时间结算一次。那么钱岂不是可以一直加下去?x代表结算次数, 计算公式: limx(1+1/x)x {lim_{x \to \infty} (1+1/x)^x}

答案是否定,最终一年后我们能得到的钱最多只能是约等于2.71828182845904523536,也就是e

综上,e的含义可以理解为增长的极限,“自然常数”的“自然”也可以理解为它是非人为的,我们只是发现了它。就像圆周率π一样,它也存在于生活的很多地方。

Copyright © qborfy 2019 all right reserved,powered by Gitbook最后修订时间: 2023-01-08 11:25:33

results matching ""

    No results matching ""