2021002130杨光飞思维导图第一章绪论

运行时间是由多种因素综合作用而决定的。首先，即使是同一算法，对于不同的输入所需的运行时间并不相同。以排序问题为例，输入序列的规模、其中各元素的数值以及次序均不确定，这些因素都将影响到排序算法最终的运行时间。

绪论

• §1.1 计算机与算法
  • 1.1.1 古埃及人癿绳索
    • 古埃及人以其复杂而浩大的建筑工程而著称于世，在长期规划与实施此类工程的过程中，他们逐渐归纳并掌握了基本的几何度量和测绘方法。
  • 1.1.2 欧几里得癿尺觃
    • 欧几里得几何是现代公理系统的鼻祖。从计算的角度来看，针对不同的几何问题，欧氏几何都分别给出了一套几何作图流程，也就是具体的算法
  • 1.1.3 起泡排序
    • D. Knuth[3]曾指出，四分之一以上的CPU时间都用于执行同一类型的计算：按照某种约定的次序，将给定的一组元素顺序排列，比如将n个整数按通常的大小次序排成一个非降序列。这类操作统称排序（sorting）。
  • 1.1.4 算法
    • 所谓算法，是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。
    • 基本操作、确定性与可行性
    • 有穷性与正确性
    • 退化与鲁棒性
  • 1.1.5 算法效率
    • 可计算性
    • 难解性
    • 子主题
• §1.2 复杂度度量
  • 1.2.1 时间复杂度
    • 运行时间是由多种因素综合作用而决定的。首先，即使是同一算法，对于不同的输入所需的运行时间并不相同。以排序问题为例，输入序列的规模、其中各元素的数值以及次序均不确定，这些因素都将影响到排序算法最终的运行时间
  • 1.2.2 渐迕复杂度
    • 至此，对于同一问题的两个算法A和B，通过比较其时间复杂度TA(n)和TB(n)，即可评价二者对于同一输入规模n的计算效率高低
    • 大O记号
    • 环境差异
    • 最坏、最好与平均情况
  • 1.2.3 空间复杂度
    • 除了执行时间的长短，算法所需存储空间的多少也是衡量其性能的一个重要方面，此即所谓的空间复杂度（space complexity）。
• §1.3 复杂度分枂
  • 1.3.1 常数O(1)
    • 问题与算法
  • 1.3.2 对数O(logn)
    • 考查如下问题：对于任意非负整数，统计其二进制展开中数位1的总数
  • 1.3.3 线性O(n)
    • 子主题
  • 1.3.4 多项式O(polynomial(n))
  • 1.3.5 指数O(2n)
    • 从多项式到指数
  • 1.3.6 复杂度局次
    • 利用大O记号，不仅可以定量地把握算法复杂度的主要部分，而且可以定性地由低至高将复杂度划分为若干层次。典型的复杂度层次包括O(1)、O(log*n)、O(loglogn)、O(logn)、O(sqrt(n))、O(n)、O(nlog*n)、O(nloglogn)、O(nlogn)、O(n2)、O(n3)、O(nc)、O(2n)等，图1.5绘出了其中七个层次复杂度函数对应的渐进增长趋势。
  • 1.3.7 输入觃模
    • 对算法复杂度的界定，都是相对于问题的输入规模而言的。
• §1.5 抽象数据类型
  • 各种数据结构都可看作是由若干数据项组成的集合，同时对数据项定义一组标准的操作。现代数据结构普遍遵从“信息隐藏”的理念，通过统一接口和内部封装，分层次从整体上加以设计、实现与使用。
• §1.4*递归
  • 1.4.1 线性递归
    • 数组求和
    • 线性递归
    • 减而治之
  • 1.4.2 递归分析
    • 递归跟踪
    • 递推方程
  • 1.4.3 递归模式
    • 递归模式
      • 多递归基
      • 实现递归
      • 多向递归
  • 1.4.4 递归消除
    • 空间成本
    • 尾递归及其消除
  • 1.4.5 二分递归
    • 分而治之
    • 数组求和
    • Fibonacci数：二分递归
    • Fibonacci数：迭代