数学基础与要分析的问题

《数据结构与算法分析Java语言描述》第一章2.1~2.3节读书笔记

1. 数学基础

1.1 定义

1 定义：如果存在正常数c和$n_0$，使得$N \ge n_0$时，$T(N) \le cf(N)$，则记为$T(N)=O(f(N))$。
  释义：T(N)的增长率小于或等于f(N)。

2 定义：如果存在正常数c和$n_0$,使得$N \ge n_0$时，$T(N) \ge cf(N)$，则记为$T(N)=\Omega(g(N))$。
  释义：T(N)的增长率大于或等于g(N)。 $\Omega$ 读作"omega"。

3 定义：$T(N)= \Theta(h(N))$当且仅当$T(N)=O(h(N))$ 和 $T(N) = \Omega(h(N))$，
  释义：T(N)的增长率等于h(N)。 $\Omega$ 读作"omega"。$\Theta$ 读作"Theta"。

4 定义：如果$T(N) = O(p(N))$且$T(N) \ne \Theta(p(N))$，则$T(N) = o(p(N))$。
  释义：T(N)的增长率小于p(N)。 读作"小o"。不同于大O，大O包含增长率相同的可能性。

1.2 法则

法则1：如果$T_1(N) = O(f(N))$且$T_2(N)=O(g(N))$,那么：

• $T_1(N) + T_2(N) = O(f(N) + g(N))$
• $T_1(N) * T_2(N) = O(f(N) * g(N))$

法则2：如果T(N)是一个k次多项式，则$T(N)=\theta(N^k)$ (T(N)的增长率与$N^K$相同)

法则3：对任意常数k，$log^kN=O(N)$，它告诉我们对数的增长非常缓慢。($log^kN$ 对数的k次方)

1.3 大O表示法

$T(N)=Of(N)$

例如$T(N)=O(N^2)$，(N平方级)，人们不说"…级的"，而说"大O…"

1. 上界：当$T(N)=Of(N)$时，保证函数$T(N)$的增速不快于$f(N)$，因此$f(N)$是$T(N)$的一个上界。
2. 下界：同上，$T(N)$是$f(N)$的一个下界。

如果$T(N)=O(N)$成立，则显然$T(N)=O(N^2)$成立，但$T(N)=O(N)$最佳。

在表示大O时，低阶项一般可以忽略，常数项也可以弃掉。

  例如：$T(N) = N/1.5 + 3$，这是一个线性函数，系数与常数项可以省略，$T(N)=O(N)$，

1.4 增长率的比较

通过计算极限$lim_{N \rightarrow \infty} (f(N)/g(N))$来确定两个函数f(N)与g(N)的相对增长率，必要时可使用洛必达法则

• 极限是0：意味着$f(N) = O(g(N))$。
• 极限是$c(常数)\ne0$，意味着$f(N) = \Theta(g(N))$
• 极限是$\infty$：意味着$g(N)=O(f(N))$
• 极限摆动：二者无关(本书中不会出现)

洛必达法则：若$lim_{N \rightarrow \infty} f(N) = \infty$且$lim_{N \rightarrow \infty} g(N)= \infty$，则$lim_{N \rightarrow \infty} f(N)/g(N) = lim_{N \rightarrow \infty} f'(N)/g'(N)$。

2. 要分析的问题

运行时间，一般分析最坏的情况。

运行空间：现代计算机而言，空间一般可以不考虑

3. 运行时间计算

计算大O的运行时间，大O是一个上界。分析的结果为程序在一定时间范围内能够终止运行提供了保证。程序可能提前结束，但绝不可能错后。

3.2 一般法则

法则1：for循环
  一个for循环的的运行时间至多是该for循环内部语句的运行时间乘以迭代次数。

法则2：嵌套for循环
  一组嵌套for循环内部的一条语句运行的总时间，为该语句运行时间乘以该组所有for循环的大小的乘积。

1
2
3
4
5

for (i=0; i<n; i++) {
    for (j=0; j<n ;j++;) {
        k++;
    }
}

  如上：每一个for循环的时间复杂度都是$O(N)$，两个嵌套则为：$O(N^2)$。

法则3：顺序语句
  将各个语句的运行时间求和即可。其中最大值就是所得的运行时间。如下程序，首先是花费$O(N)$，接着是$O(N^2)$，因此总量也是$O(N^2)$。

1
2
3
4
5
6
7
8

for (i=0; i<n; i++) {
    a[i] = 0;
}
for (i=0; i<n; i++) {
    for(j=0; j<n; j++) {
        a[i] += a[j] + i + j;
    }
}

法则4：if/else语句
  一个if/else语句的运行时间从不超过判断的运行时间再加上S1和S2中运行时间长者的总运行时间。

3.3 其他情形

  显然，分析的策略是从内部向外开展，如果有方法调用，那么首先需要分析这些方法调用。如果有递归过程，有以下几种可能。

1. 实际是for循环的递归：如下，分析很简单，本质上就是一个O(N)的复杂度。

1
2
3
4
5
6
7

public static long factorial(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

2. 普通正常的递归：实际上正常使用的递归，转换成一个循环结构是非常困难的。如下程序，它递归的使用效率非常低。

1
2
3
4
5
6
7

public static long fib(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

  该程序的效率实际上非常低。令$T(N)$为调用函数fib(n)的运行时间。 $T(N) = fib(n)$
分析：

1. 如果N=0或N=1，则在第2行即可执行完毕，则可以说T(0)=T(1) =1。

2. 若N>2，则执行该方法的时间是第2行的常数工作加上第5行的工作，第5行由一次加法和两次方法调用组成。

3. 方法调用必须使用他们自己来分析他们，第一次方法调用是fib(n-1),按照T的定义($T(N) = fib(n)$)，它需要T(N-1)个时间单元。类似，第二次方法调用需要T(N-2)个时间单元。

4. 此时总的时间需求为T(N-1) + T(N-2) + 2，其中2指第二行的工作加上第五行的加法，于是对于$N \ge 2$，有下列运行时间公式。

   $T(N) = T(N-1) + T(N-2) + 2$

   但是$fib(N) = fib(N-1) + fib(N-2)$ (由程序的递归条件可以确定)，因此由归纳法容易证明，$T(N) \ge fib(N)$ 。在1.2.5节证明过$fib(N) < (5/3)^N$ (斐波那契数列)，类似,可以证明$fib(N) \ge (3/2)^N \quad N>4$；从而证明这个的运行时间以指数速度增长。

   该递归耗时长的原因是违背了递归的第四条主要规则合成效益法则。因为在$fib(n) = fib(n-1) + fib(n-2)$已经计算一次$fib(n-2)$了，$fib(n-1)$又要计算一次。违背了格言"计算任何事情不要超过一次"。

3.4 最大子序列和问题的求解、

子序列之和：给定一个数组，例如[-1,-2,5-3,8,-1]，则最大子序列之和为10 ：5+(-3)+8
子序列：原数组中连续的数组成新的数组

  叙述四个算法求解提出的最大子序列和问题。

3.4.1 算法一

  如下算法穷举所有的可能。本算法并不计算实际的子序列，实际的计算还要添加一些额外的代码。

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

public static int maxSubSum1(int[] a) {
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {    // 确定算的起始位置	
            for (int j=i; j<a.length; j++) {    // 确定计算求和的范围
                int thisSum = 0;                // 记录临时值，确定是否比最大值大
                for (int k = i; k <= j; k++) {  // 确定该范围内的子序列的和的值。(实际上结果只有一个子序列)
                    thisSum += a[k];            
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

  该算法的三个嵌套for循环都是O(N),所以最终的时间复杂度为$O(N^3)$。忽略常数与低阶项。
精确分析由 $\sum_{i=0}^{N-1} \sum_{j=i}^{N-1} \sum_{k=i}^j 1$ 得到。该"和"指出程序被执行多少次被执行。从内向外求值。特别地，将用到前N个整数求和与前N个平方数的和公式。

首先有

$\sum _{k=i}^j 1 = j-i+1 \quad (j-i+1个1相加)$

得到

$\sum _{j=i} ^{N-1} (j-i+1) = \frac{(N-i+1)(N-i)}{2} \quad (带入可得从1+2+3...+N-i)$

还有
第一行理解：令i=i-1，求和下标 i-1=0->i=1，上标 i-1=N-1->i=N。

$\begin{aligned} \sum _{i=0} ^{N-1} {\frac{(N-i+1)(N-i)}{2}} &= \sum_{i=1}^N \frac{(N-i+1)(N-i+2)}{2} \\ &= \frac{1}{2} \sum_{i=1}^N i^2-(N+\frac{3}{2}) + \frac{1}{2}(N^2+3N+2)\sum_{i=1}^N 1 \\ &= \frac{1}{2}\frac{N(N+1)(2N+1)}{6}-(N+\frac{3}{2})\frac{N(N+1)}{2}+\frac{N^2+3N+2}{2}N\\ &= \frac{N^3+3N^2+2N}{6} \end{aligned}$

3.4.2 算法二

  如下算法具有$O(N^2)$的复杂度。
该算法的区别在于，发现不需要使用确定起始位置，只需要求和子序列的起始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void main(String[] args) {
    int[] a = {1, -4, 5, -3, 6, 9, -4, -7, 6};
    int res = maxSumSub2(a);
    System.out.println(res);
}

public static int maxSumSub2(int[] a) {
    int maxSum = 0;
    // 确定子序列求和范围的起始位置
    for (int i = 0; i <a.length ; i++) {
        int thisSum = 0;
        // 确定子序列的终止位置
        for (int j = i; j < a.length; j++) {
            thisSum += a[j];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            }
        }
    }
    return maxSum;
}

3.4.3 算法三

  如下递归算法具有$O(NlogN)$的复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

public static void main(String[] args) {
    int[] a = {1, -4, 5, -3, 6, 9, -4, -7, 6};
    int res = maxSumRec(a, 0, a.length-1);
    System.out.println(res);
}

public static int maxSumRec(int[] a, int left, int right) {
    // 递归的出口
    // 如果left==right，说明只有一个元素，返回该元素或0即可
    if (left == right) {
        if (a[left] > 0) {
            return a[left];
        } else {
            return 0;
        }
    }

    // int center = (left + right)/2;
    // 推荐，避免和超出int最大范围的可能
    int center = left - (left -right)/2;
    // 提前递归调用，因为递归到底的时候不需要做额外的处理，例如交换
    // 递归获得左半的最大子序列和
    int maxLeftSum = maxSumRec(a, left, center);
    // 递归获得右半的最大子序列和
    int maxRightSum = maxSumRec(a, center+1, right);

    // 初始化递归二分时，左边连着center的最大值
    int maxLeftBoarderSum = 0;
    int leftBoarderSum = 0;
    for (int i = center; i >= left ; i--) {
        leftBoarderSum += a[i];
        if (leftBoarderSum > maxLeftBoarderSum){
            maxLeftBoarderSum = leftBoarderSum;
        };
    }

    // 同上，初始化右边连着center+1的最大值
    int maxRightBoarderSum = 0;
    int rightBoardSum = 0;
    for (int j = center+1; j <=right ; j++) {
        rightBoardSum += a[j];
        if (rightBoardSum > maxRightBoarderSum) {
            maxRightBoarderSum = rightBoardSum;
        }
    }

    // 从而获取每一个递归的部分的最大值
    // 以一个最小的但长度不为1部分举例，这个递归部分会得到三个最大值，
    // 一分为二的左边的最大值maxLeftSum，右边的最大值maxRightSum，中间部分的最大值：maxLeftBoarderSum + maxRightBoarderSum
    // 返回其中的最大值，这个最大值又会作为上一级递归的左边或者右边的最大值，
    // 递归返回到最上级的时候，结束，获取到此最大值
    return max3(maxLeftSum, maxRightSum, maxLeftBoarderSum + maxRightBoarderSum);
}

public static int max3(int a, int b, int c) {
    int max = Math.max(a, b);
    max = Math.max(max, c);
    return max;
}

1.递归的正确性分析：

1. 该算法采用递归的分治思想，将数组一分为二去计算，因为最大子序列只可能在三处地方出现：二分后的左半部分，二分后的右半部分，二分后的左半与右半的连接部分。
2. 对于第三种情况，可以将前半部分的最大和(从center–)加上后半部分的最大和()从center++得到。
3. 最后比较这三个最大值，即可得到真正的最大值。

3.4.4 算法四

   如下递归算法具有$O(N)$的复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static void main(String[] args) {
    int[] a = {1, -4, 5, -3, 6, 9, -4, -7, 6};
    int res = getMaxSubSum4(a);
    System.out.println(res);
}

public static int getMaxSubSum4(int[] a) {
    // 初始化最大值，当前子序列的值
    int maxSum = 0, thisSum = 0;
    for (int j = 0; j < a.length; i++) {
        // 当前子序列的值加上下个的值
        thisSum += a[j];
        if (thisSum > maxSum) {
            maxSum = thisSum;
        } else if (thisSum < 0) {
            // 如果加后，thisSum小于0，则thisSum必定小于maxSum
            // 如果thisSum += a[j]后，thisSum小于0，则说明最大的子序列不在这里结束与开始(因为有负数)，所以也不改变之前记录的maxSum
            // 如果小于0，将thisSum置为0，从新开始计算之后的最大子序列，如果有比maxSum还大的，则赋值
            thisSum = 0;
        }
    }
    return maxSum;
}

1.算法的正确性分析：

1. j代表当前序列的终点，如果a[i]到a[j]的和是负的，那么可以将i推进到j+1，
2. 令下标：0<i<j，如果thisSum的0到i的和>0，那么，thisSum = a[0] + …+a[i]，如果thisSum为0，则说明，从a[i]开始的子序列不是最优解了。因为如果存在一个最大值从a[i]开始，或包含a[i]，由于thisSum为负，a若[i+k]为正，则继续从a[i+k]一定更优。将thisSum置为0，则之后的最大值从a[i+1]开始，算的值再与maxSum比较，从而得到真正的最大值。

2.联机算法：

  在任意时刻，只需要对操作的数据读入一次，一旦a[i]被读入并处理，它不在需要被记忆。在任意时刻，算法都能对已经读入的数据给出对应的子序列的正确问题答案。而且仅需要常量空间并以线性时间运行。

3.5 运行时间的对数

一般法则：如果一个算法用O(1)的时间把问题削减为其一部分(通常为1/2)，那么该算法就是O(logN)。
如果一个算法使用常数的时间，将问题复杂度减少一个常数量，那么为O(N)

3.5.1折半查找

折半查找(binary search)：给定一个整数X和一组已经在内存中且已经排好序的整数数组$A_0,A_1,...,A_{n-1}$$,求有下标i使$$A_i=X$,如果不存在则返回 i = null。

由于该数组已经排序好，因此采用折半查找：
  先查找数组居中的元素，如果等于X，则找到。如果比X小，说明结果在居中数组的右边。比X大则说明在居中数组的左边。循环时间最多为$log(N-1) + 2$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class BinarySearch {
    public static void main(String[] args) {
        // String实现了Comparable接口，所以可以使用，但是int是基本类型没有实现，Integer有实现
        String[] arr = {"1", "2", "3", "6", "12", "18", "20"};
        String stringSearch = getBinarySearch(arr, "6");

        Integer[] brr = {1,2,3,4,6,8,10,14,18};
        Integer b = 10;
        Integer integerSearch = getBinarySearch(brr, b);
        System.out.println(stringSearch);
        System.out.println(integerSearch);
    }

    // 返回T类型，同时限定T的类型
    // <T extends Comparable<? super T>>限定了T或T的父类具有可比较(Comparable类)的能力
    // T必须继承Comparable接口，或<? super T>规定了T或T的父类继承了Comparable
    public static <T extends Comparable<? super T>> T getBinarySearch(T[] a, T x) {
        int low = 0;
        int high = a.length -1;
        // 基线条件low<high
        while (low <= high) {
            int mid = low + (high-low)/2;
            if (a[mid].compareTo(x) < 0) {
                // 如果a[mid] < x
                low = mid+1;
            } else if (a[mid].compareTo(x) > 0) {
                // 如果a[mid] > x
                high = mid - 1;
            } else {
                // 如果a[mid] = x，这里返回x，因为类型为T
                return x;
            }
        }
        // 不存在，不确定T的类型，返回null
        return null;
    }
}

3.5.2欧几里得算法(辗转相除法)

计算两个数的最大公因数，如gcd(50, 15) = 5

欧几里得算法(辗转相除法)：gcd(a, b) = gcd(b, a%b) a>=b; gcd(a,b)表示a、b的最大公因数

1
2
3
4
5
6
7
8
9
10

public static long getGcd(long m, long n) {
    //由于java取余的特性，如果m < n,第一次循环会交换m，n
    // 例：5，10；5%10=0...5, 之后，m=5，n=10
    while (n != 0) {
        long rem = m % n;
        m = n;
        n = rem;
    }
    return m;
    }

这是一个快速的算法，如下将证明经过两次迭代后，余数最多是之的一半，从而证明迭代次数至多为$2O(logN)$

定理1：如果M>N，则M mod N < M/2 (注意java中取余取mod的区别)
证明：
  情形1：如果$N\le M/2$，则由于余数一定小于除数N，故$余数\le N \le M/2$。
  情形2：如果$N > M/2$，且$N<M$，所以M一定只包含一个N，从而$余数=M- 1 \times N$，而$N > M/2$，所以余数< M/2。

  由此可知，M经过两次欧几里得算法后，M变成M%N的余数，故需最坏的情况要2logN的复杂度。实际上该算法的平均复杂度需要大量的复杂计算，其平均迭代次数约为$(12 ln2 lnN)/\pi^2 + 1.47$

幂运算

  计算$X^N$的明显的算法是使用N-1次乘法自乘，有一种递归算法更好：$N\le 1$是递归的基准情形。否则，若N为偶数，我们有$X^N = X^{N/2} \cdot X^{N/2}$，如果N是奇数，则有$X^N = X^{(N-1)/2} \cdot X^{(N-1)/2} \cdot X$，一直递归下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public static void main(String[] args) {
        BigInteger pow = pow(new BigInteger("3"), 100);
        System.out.println(pow);
        // Math工具类已经实现了，不过限定为double类型(参数业务double)
        double pow1 = Math.pow(3.0, 2.0);
        System.out.println(pow1);
    }

    public static BigInteger pow(BigInteger x, int n) {
        if (n == 0) {
            return new BigInteger("1");
        }
        if (n == 1) {
            return x;
        }
        if (isEven(n)) {
            return pow(x.multiply(x), n / 2);
        } else {
            return pow(x.multiply(x), n/2).multiply(x);
        }
    }
    // 判断是否为偶数
    private static boolean isEven(int n) {
        return n % 2 == 0;
    }