数据结构与算法分析 引论

数据结构与算法分析

---

写在开头

emmm……因为转专业考试笔试结束之后还要面试，所以……还是继续写一篇编程方向的读书笔记好了
本学期预计要看完（在下学期开学之前）两本编程方向的书
一个是《数据结构与算法分析》另外一个是《离散数学及其运用》
数码方向要看《摄影的骨头》
以后肯定要向IT发展，但是方向还没有确定下来。
这个在大二上学期确定，到底是做前端开发还是做后端，做web开发还是做安卓开发（仅仅是举个例子，具体的到时候再说吧。）
到时候会结合工作室的优势和我自己的处境等因素综合做决定。

第一章 引论

1. 本书讨论的内容

评估并优化代码所利用的时间和空间

2. 数学知识复习

这里都是一些很简单的数学知识，比如指数，对数，求模都知道了。
下面写一下我不知道的东西。

2.1 级数

$$\sum_{i=0}^N 2^i=2^{N+1}-1$$
$$\sum_{i=0}^N A^i=\frac{A^{N+1}-1}{A-1}$$
以上为“几何级数”的公式
（这一部分告诉还没学过，所以拿出来单独写一下）
具体的证明方法和简单，，这里就不很详细的写了
大致上是利用高中常用的错位相减法（这种运算只能对收敛的级数进行）进行运算
然后又介绍了一下算数级数
$$\sum_{i=1}^N i=\frac{N(N+1)}{2}\approx\frac{N^2}{2}$$
$$\sum_{i=1}^N i^2=\frac{N(N+1)(2N+1)}{6}\approx\frac{N^3}{3}$$
$$\sum_{i=1}^N i^k\approx\frac{N^{k+1}}{\mid k+1\mid}$$
(当k=-1时上面一个公式不成立）

$$H_N=\sum_{i=1}^{N}\frac{1}{i}\approx log_e N$$
以上公式中，$H_N$被称为调和数，在近似式中，误差趋近于$\gamma=0.57721566$，这个值被称为欧拉常数。

3. 递归简论

递归的四个基本原则
1. 基准情形
必须总有某系基准情形，他无需递归就能解出
2. 不断推进
对于那些需要递归求解的情形，每一次递归调用都必须要使求解状况朝接近基准情况的方向推进
3. 设计法则
假设所有递归调用都能运行（要吐槽一下这本书的翻译，让人看得有些云里雾里的，译者明显不是搞编程的……）
递归没办法追踪递归调用的序列，而且有大量的隐含系统开销。
4. 合成效益法则
在求解同一个问题的实例中，切勿在不同递归中调用重复性工作。
大致上来说，作者要表达的意思是：
递推要在合理的时候结束，不能无穷递归
每一次递归过后，都要朝着结束递归的方向前进（还是不能无穷递归）
在设计递归函数的时候，不用考虑函数运行的具体细节。
递归的原理为数学中的归纳法。
（第四点不知道，作者说会在下面讲）

---

之前因为从来没有用过递归……所以对递归一直都是一头雾水……
但是用了几次之后发现递归还是挺好用的，代码也很直观
下面给出一个运用递归的例子：
这是周六曹睿之大佬出的小测的第二题
T29373 分解质因数

// 2分解质因数.cpp: 定义控制台应用程序的入口点。
//
#include<stdio.h>
int solve(int a);
int main()
{
    int a, b,num;
    scanf("%d %d", &a, &b);
    while (a <= b)
    {
        num = a;
        printf("%d=", a);
        int counter = 2;
        while (num / counter*counter != num)//检测num是否可以整除…利用了int类型会截断小数部分的性质……这个方法感觉有些蠢……用一个求模会好一些
        {
            counter++;
        }
        printf("%d", counter);
        num = num / counter;
        if (num == 1);
        else
            solve(num);
        a++;
        putchar('\n');
    }
    return 0;
}
int solve(int a)
{
    int counter = 2;
    while (a / counter*counter != a)
    {
        counter++;
    }
    printf("*%d", counter);
    a = a / counter;
    if (a == 1)
        return 0;
    else
        solve(a);
}

在这个例子中，反复用到了solve函数
基准情况：1只能被1整除
不断推进：a每一次都会减小，最后会减小到1，结束递归
设计法则：emm……递归代码没毛病，而且空间占用为线性占用（不是指数级的占用）