算法导论学习笔记（1）

《算法导论》一共包含两部分，即算法分析和算法设计。

什么是算法分析？

“算法分析是关于计算机程序性能和资源利用的理论研究。”

可以理解为，算法的主要目的是为了提升性能和资源利用，那么，在程序设计方面，有没有比性能更重要的呢？当然有，正确性、简洁性、稳定性、安全性、可扩展性、功能性、可维护性、模块化、用户体验等等，在程序设计方面都很重要，那么，为什么要学习算法呢？

为什么要学习算法呢？

有以下三点理由：

1. 在绝大多数情况下，性能的好坏会直接决定方案的可实施性。
2. 算法是计算机科学领域中描述程序行为的语言，是一种让程序更为简洁的思考方式，其所扮演的角色就如同经济中的货币。
3. 有趣。（有趣的定义千差万别，有趣的事情千人千面）

复杂度分析的一些概念

• 基本操作：内存引用计数，即程序实际上访问了某个变量多少次。
• 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。这是分析中最常用的指标。
• 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。事实上，这通常被认为是一种假象，因为最好情况下的输入是特定的，并不能真正检验程序的实际表现，而且很容易“作弊”。
• 平均时间复杂度：代码在所有情况下出现的概率的加权平均值。在一些情况下，会使用这项指标。这里其实还有一个问题，即如何知道各种情况出现的概率？答案是做一个输入统计分布的假设，最常见的输入统计分布的假设是所有输入以等可能性的方式出现，即均匀分布。
• 渐近分析：基本思路有两点：1.忽略掉那些依赖于机器的常量；2. 不是去检查实际的运行时间，而是去关注运行时间的增长。渐近分析的结果用渐近符号 （与其说它是一个运算符，不如说它是一个描述符）表示， 的计算方式为丢弃低阶项，并忽略前面的常数因子，这里有一个例外，就是当数据量 n 很大，大到计算机无法运行该算法时，一些相对低速的算法可能更好，因为它们在合理规模的输入下运行得更快。因此，我们需要在数学理解和和工程直觉之间做出权衡，才能写出好用的程序。

插入排序

插入排序将数据分为两个区间，已排序区间和未排序区间。核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。插入排序的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，是一个原地排序算法。

Go 语言实现如下：

// 插入排序
func insertionSort(list []int) []int {
    n := len(list)
    a := make([]int, n, n)
    copy(a, list) // 不改变原切片值
    if n <= 1 {
        return a
    }
    for i := 1; i < n; i++ {
        v := a[i]
        j := i - 1
        for ; j >= 0; j-- {
            if a[j] > v {
                a[j+1] = a[j]
            } else {
                break
            }
        }
        a[j+1] = v
    }
    return a
}

归并排序

归并排序有三个步骤：

1. 如果 n 等于 1，结束；
2. 递归地对 A[1 到 n/2 向上取整]这部分，以及 A[n/2+1 向上取整到 n]部分排序；
3. 对排好序的两个表做归并操作。

Go 语言实现如下：

func mergeSort(list []int) []int { // 递归地对 A[1 到 n/2 向上取整]这部分，以及 A[n/2+1 向上取整到 n]部分排序
    if len(list) <= 1 { // 如果 n 等于 1，结束
        return list
    }
    mid := len(list) / 2
    left := mergeSort(list[0:mid])
    right := mergeSort(list[mid:])
    res := merge(left, right) // 对排好序的两个表做归并操作
    return res
}

func merge(list1, list2 []int) []int { 
    res := make([]int, 0, len(list1)+len(list2))
    i, j := 0, 0
    l, r := len(list1), len(list2)
    for i < l && j < r {
        if list1[i] > list2[j] { // 每次只关注两个元素
            res = append(res, list2[j])
            j++
        } else {
            res = append(res, list1[i])
            i++
        }
    }
    res = append(res, list2[j:]...)
    res = append(res, list1[i:]...)
    return res
}

构造递归树的过程如下：

T(n) = 2T(n/2) + cn // c 是大于 0 的常数
T(n/2) = 2T(n/4)+cn/2 
T(n/4) = 2T(n/8)+cn/4
...

递归树

递归的过程中，会形成一个递归树，每次递归的过程都是等分，直到 n 等于 1 为止，即所有叶子节点都是 T(1)，即 。此时，可以得出，n 折半的次数就是树的高度，也就是 的常数倍，整个树共有 n 个节点。

对比

从渐近分析角度考虑，归并排序的性能远高于插入排序，因为 的算法的比 增长的慢，但在实际中，数据规模较小时，插入排序是一个完美优雅的可用排序算法（30 是一个分水岭）。

课程源

算法导论-麻省理工