附录 I 数学基础与算法设计原则#

1. 基础数学#

1.1 等幂求和#

• 证明 (递归差分法)

下面是 \(k\ge0\) 时的情况. 观察这样一个式子: \(P_n(x)=(x+1)^n-x^n(n\ne1)\). 以 \(n=3\) 时为例: \(P_3(x)=(x+1)^3-x^3=3x^2+3x+1\), 可以进行如下变形:

用上面的方式我们便得到了平方求和的公式. 同理, 我们猜想当 \(n > 3\) 时同样可用类似方法. 对任意 \(n > 0\), 根据二项式定理展开得到:

接下来, 我们在递归的前提下已经知道前 \(n-2\) 次幂的所有求和公式. 据此即可推导出 \(n-1\) 次幂的求和公式.

不难发现, 对于任意 \(\sum_{x=1}^{N}x^{n-1}\), 其最高次项都是 \(\frac{N^n}{n}\). 因此, 在 \(N\) 足够大时, 有:

上面只说明了 \(k\ge0\) 时的情况. 对于 \(k < 0\), 首先确定是否存在可精确表达的初等函数闭式形式. 我们考虑一个满足前述形式的函数 \(F\), 使得 \(F(N)-F(N-1)=\frac{1}{N^p}\). 若存在, 即可计算: \(\sum_{N=2}^{n}(F(N)-F(N-1))=\sum_{N=2}^{n}\frac{1}{N^p}\)

显然, 若 \(F(x)\) 中存在无理项, 则必须在 \(F(N)-F(N-1)\) 式中永久被恰好抵消, 否则不满足右式恒为有理数的前提. 据此, \(F(x)\) 中的无理函数部分无关紧要, 我们只需要考虑 \(F\) 中的有理函数部分.

首先, 由于右侧式子不存在多项式, 若左侧存在则必须恰好抵消, 所以同样我们只需要考虑 \(F\) 为真分式表达式的情况. 对于任意真分式, 我们知道必定存在一个 \(N\) 使得 \(F(N)\) 的分母 \(A(N_0)\) 为 \(0\), 也就是未定义点. 对于 \(F(N)-F(N-1)\), 则必然至少存在两个未定义点, 并且 \(F(N-1)\) 的未定义点恰好在 \(F(N)\) 未定义点的右侧, 两点在坐标系上距离为 \(1\). 而对于 \(\frac{1}{N^p}\), 显然只存在一个未定义点. 综上所述, 这样的初等函数闭式形式并不存在.

据此, 我们关注该式的估计形式. 利用积分判别法思想:

因此, 在 \(n\) 足够大时, 不论正负, 有:

1.2 复杂度计算基础#

其一, 若 \(T_1(N)=O(f(N))\) 且 \(T_2(N)=O(g(N))\), 则:

• \(T_1(N)+T_2(N)=\max(O(f(N)), O(g(N)))\)
• \(T_1(N)\times T_2(N)=O(f(N)\times g(N))\).

其二, 对于任意常数 \(k\), 有: \(\log^kN=O(N)\).

1.3 算法复杂度分析法则#

• for 循环:

1
2

for (int i = 0; i < N; i ++)
    c += i;

复杂度就是循环次数 \(O(N)\)

• 嵌套的 for 循环:

1
2
3

for (int i = 0; i < N; i ++)
    for (int j = 0; j < N; j ++)
        c += j * i;

复杂度就是循环次数乘以更深的循环次数 \(O(N^2)\)

• 顺序语句复杂度计算

1
2
3
4
5
6

for (int i = 0; i < N; i ++)
    c += i;

for (int i = 0; i < N; i ++)
    for (int j = 0; j < N; j ++)
        c += j * i;

复杂度为 \(\max (O(N) ,O(N^2))=O(N^2)\)

• if/else 语句

1
2
3
4

if (A1)
    B1
else
    B2

复杂度为 \(\max (O(B1), O(B2))\)

• 递归调用(可改写为循环结构类)

使用 for 循环复杂度计算方法即可.

• 递归调用(不可改写为循环结构类)

2. 算法设计原则#

• 收敛性: 所有调用结果最终必须可归于某些基准情形. 换言之, 最后一轮所有可能的函数调用返回值是确定的, 与函数传入的值无关.
• 单调性: 任何一轮的调用方向都是唯一确定的. 准确的说, 是朝着那些基准情形的方向进行的.
• 完备性: 任何设计算法中确定合法的输入值都有唯一确定的处理情况, 并且中途调用函数的返回值同样是合法的.
• 合成效益法则: 求解某个问题的同一实例时不要二次计算, 浪费算力.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <bits/stdc++.h>

using namespace std;

int fib(int x) {
    if (x <= 1)
        return x;
    else
        return fib(x - 1) + fib(x - 2);
}

int main(void) {
    print(fib(6));

    return 0;
}

flowchart TD
    n6["fib(6)"] --> n5["fib(5)"]
    n6 --> n4["fib(4)"]

    n5 --> n4_2["fib(4)"]
    n5 --> n3["fib(3)"]

    n4 --> n3_2["fib(3)"]
    n4 --> n2["fib(2)"]

    n4_2 --> n3_3["fib(3)"]
    n4_2 --> n2_2["fib(2)"]

    n3 --> n2_3["fib(2)"]
    n3 --> n1["fib(1)"]

    n3_2 --> n2_4["fib(2)"]
    n3_2 --> n1_2["fib(1)"]

    n3_3 --> n2_5["fib(2)"]
    n3_3 --> n1_3["fib(1)"]

    n2 --> n1_4["fib(1)"]
    n2 --> n0["fib(0)"]

    n2_2 --> n1_5["fib(1)"]
    n2_2 --> n0_2["fib(0)"]

    n2_3 --> n1_6["fib(1)"]
    n2_3 --> n0_3["fib(0)"]

    n2_4 --> n1_7["fib(1)"]
    n2_4 --> n0_4["fib(0)"]

    n2_5 --> n1_8["fib(1)"]
    n2_5 --> n0_5["fib(0)"]

Comments