一、算法-数学基础

指数运算

• X^A * X^B = X^A+B
• X^A / X^B = X^A-B
• (X^A ) ^B = X^AB
• X^A + X^A = 2X^A
• 2^A + 2^A = 2 * 2^A = 2^A+1

对数运算

• X^A = B，则 A = log_XB。如：2³ = 8，则 3 = log₂8；4³ = 64，则 3 = log₄64；
• log₂8 通常简写为log8，所有以2为底数的对数，2都可以简写。以其他数为底数的对数，底数不能简写。
• logAB = logA+logB，A，B>0；如：log(8*4) = log8+log4 = 3+2 = 5 = log32，32 = 2⁵
• logA/B = logA-logB，A，B>0；如：log(8/4) = log8-log4 = 3-2 = 1 = log2，2 = 2¹
• log_AB = (log_CB) / (log_CA),A,B,C>0,A不等于1
  证明：
  令：X = log_AB，Y = log_CB，Z = log_CA，有X= Y / Z
  so：B = A^X , B = C^Y, A = C^Z
  代入：B = （C^Z)^X = C^Y
  得：ZX = Y
• log(A^B)=BlogA。（ log(A * A * A.....*A) = logA+logA+....+logA = BlogA )
• 对于所有的X>0，logX < X

级数运算

• 2⁰+2¹+2²+....2ⁿ = 2ⁿ⁺¹-1
• 当A>1时，A⁰+A¹+A²+....Aⁿ = (Aⁿ⁺¹-1) / (A-1)
  证明：
  S = A⁰+A¹+A²+....Aⁿ
  AS = A¹+A²+....Aⁿ+Aⁿ⁺¹
  S - AS = A⁰ - Aⁿ⁺¹
  S = (Aⁿ⁺¹-1) / (A-1)
• 当0<A<1时，A⁰+A¹+A²+....Aⁿ <= 1/(1-A)
  证明：
  S = A⁰+A¹+A²+....Aⁿ
  AS = A¹+A²+....Aⁿ+Aⁿ⁺¹
  S - AS = A⁰ - Aⁿ⁺¹
  S = (1 - Aⁿ⁺¹) / (1 - A)
  此时，由于A<1,所以 Aⁿ⁺¹当n趋向于无限大时，Aⁿ⁺¹无限趋向于0，因此S <= 1 / (1 - A)
• 1+2+3+...+n = n(n+1)/2
  证明：
  S = 1 + 2 + 3 +...+ n-2 + n-1 + n
  S = n + n-1 + n-2 +...+3 + 2 + 1
  相加：
  2S= n+1 + n+1 +....+ n+1 = n(n+1)
  S = n(n+1)/2