算法设计与分析

数据结构

算法设计

算法分类

搜索、排序、插入、更新、删除

算法特点

明确、输入、输出、有限性、可行性、独立

算法分析

算法分析

先验分析、后验分析

复杂度

时间因素、空间因子

空间复杂度

算法在其生命周期中的内存空间量，主要包括：
固定部分，存储某些数据和变量所需的空间，与问题大小无关；
变量部分，取决于问题的大小，如动态内存分配，递归堆栈空间等。
空间复杂度S（P）是S（P）= C + SP（I），其中C是固定部分，S（I）是算法的可变部分，取决于实例特征I。

时间复杂度

算法完成所需时间量，时间T（n），其中T（n）可以测量为步数，只要每步消耗的时间恒定。

算法时间分析

O(n)运行时间上限形式化方法
Ω(n)算法运行时间下线形式化方法
θ(n)算法运行时间的下限和上限的形式化方法

分而治之

将问题分成若干子问题，所有子问题的解决方案合并成原始问题的解决方案。

分隔

子问题分割成原子性问题。

解决

小问题的解决。

合并

子问题解决后递归结合，得到原始问题的解决方案。

递归

函数自行调用

def bsearch(list, idx0, idxn, val):
    if (idxn < idx0):
        return None
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value
        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval
list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

回溯

回溯属于递归的一种形式，涉及任何可能性的唯一选择，先指定唯一退出状态选项。

def permute(list, s):
    if list == 1:
        return s
    else:
        return [ y + x
                 for y in permute(1, s)
                 for x in permute(list - 1, s)
                 ]
print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))

算法类

贪婪算法

寻找局部最优解：
旅行推销员问题
Prim的最小生成树算法
克鲁斯卡尔的最小生成树算法
Dijkstra的最小生成树算法

分而治之算法

问题分解，解决方案合并：
合并排序
快速排序
克鲁斯卡尔的最小生成树算法
二进制搜索

动态编程

对问题进行全面优化，将尝试检查解决问题的结果：
斐波那契数列
背包问题
河内塔