为什么需要算法分析？

在求解问题时，我们既需要得到正确的答案（正确性），也需要尽可能快地完成求解（性能）。一个正确的但运行时间极长的程序是不切实际的，我们真正需要的是正确且高效的程序。通过算法分析，我们可以找到程序的性能瓶颈并对程序进行性能优化。

基本数学运算

指数

指数的运算法则

  • \[X^{A}X^{B}=X^{A+B}\]
  • \[\frac {X^{A}}{X^{B}}=X^{A-B}\]
  • \[(X^A)^B = X^{AB}\]

对数

对数的定义：\(X^A = B 当且仅当 log_xB = A\)

根据指数的运算法则和对数的定义，可以证明如下对数运算法则

  • \[log_AB = \frac {log_cB}{log_cA}, A,B,C > 0, A \neq 1\]
  • \[log \frac{A}{B} = logA - logB\]
  • \[log(A^B)=BlogA\]

级数

常用的级数有几何级数和算术级数

  • 几何级数 \(S = \sum_{i=0}^{N} A^i = \frac{A^{N+1} - 1}{A - 1}\)

使用错位相减进行推导

\[S=1+A+A^2+A^3 + A^4 + ... + A^N\] \[AS=A+A^2+A^3 + A^4 +A^5 ... + A^{N+1}\] \[AS - S=A^{N+1} - 1\] \[S=\frac{A^{N+1} - 1}{A-1}\]
  • 算术级数 \(S = \sum_{i=0}^{N} i = \frac{(N+1)N}{2}\)

使用倒序相加的方法进行推导

\[S = \sum_{i=0}^{N} i = 1+2+3+...+N\] \[S = \sum_{i=0}^{N} i = N+N-1+N-2+...+1\] \[2S = \sum_{i=0}^{N} (N+1) = (N+1)N\] \[S = \sum_{i=0}^{N} (N+1) = \frac{(N+1)N}{2}\]

模运算

如果N整除A-B，那么就说A与B模N同余，记为\(A \equiv B(mod N)\)，这意味着无论是A还是B被N所除，得到的余数都是相同的。

当\(A \equiv B(mod N)\)时，有如下法则

  • \[A + C \equiv B + C(mod N)\]
  • \[AD \equiv BD(mod N)\]

如何证明

证明定理成立常用方法有归纳法和反证法

  • 归纳法

第一步先证明基准情形，证明定理对一个确定的值成立。这一步相当于证明定理成立的起点

第二步进行归纳假设，假设定理对有限数K成立，根据这个假设证明定理也对K+1成立。这一步相当于对定理的正确性在相邻数字上进行递推

  • 反证法

以“前提条件 → 结论”的形式对定理进行表述

先假设结论不成立，然后找出结论不成立时与前提条件的矛盾，从而证明前提条件成立时结论必须成立

证明定理不成立的方法是举出一个反例

递归

当一个函数的定义包括它自身时就称之为递归的。

递归的简洁是以系统的函数调用开销为代价的，函数调用栈会负责簿记各个递归函数的状态。

递归的四条基本法则

  • 基准情形。必须要有某些情形可以直接得出解
  • 不断推进。每一次递归求解都要朝着基准情形推进（否则会出现死循环）
  • 设计法则。假设所有的递归调用都能运行（不会爆栈）
  • 合成效益法则。递归求解时不会重复求解同一个问题（一个问题只求解一次）

因为递归的前两条法则与归纳法的证明过程十分相似，所以递归算法正确性的证明常常会用到归纳法

猜您还喜欢