数据结构-算法思维导图

一篇关于数据结构-算法思维导图，@算法是对特定问题求解步骤的一种描述。@算法是指令的有限序列，是求解问题的有限步骤的序列，其中每个指 令表示一个或多个操作。

算法

• 概念
  • ①算法是对特定问题求解步骤的一种描述。②算法是指令的有限序列，是求解问题的有限步骤的序列，其中每个指令表示一个或多个操作。
• 特点
  • 有穷性
    • 一个算法能在有限步后和有限时间内执行结束。
  • 确定性
    • ①算法中的每一条指令必须有确切的含义，没有二义性。②在任何条件下，只有唯一的一条执行路径。即对于相同的输入，必须产生相同的输出。
  • 可行性
    • 算法中描述操作是可行的。算法中的描述操作可以通过已实现的基本操作的有限次运算来实现。
  • 有输入
    • 一个算法有零个或多个输入。
  • 有输出
    • 一个算法有一个或多个输出。
• 要求
  • 正确性
    • ①正确性指不含语法错误。②正确性应能满足具体问题的要求，可以正确反映需求。
  • 可读性
    • ①可读性指算法供人们阅读的方便程度。②可读性好有助于人们对算法的理解。
  • 健壮性
    • ①健壮性主要指对出错情况或异常情况的处理能力。②当输入数据非法时，算法也能做出适当的处理，而不是出现莫名其妙的输出结果。
  • 效率和存储量要求
    • ①效率描述的是算法的执行时间，存储量指的是算法执行过程中所需要的最大存储容量空间。②要求花费尽量少的时间和尽量低的存储要求。
• 估量
  • 评估概念
    • ①评价一个程序算法的优劣最重要的依据是看这个程序的执行时间需要占用多少机器资源，在各种机器资源中，最重要的是时间资源和空间资源。②因此在进行程序分析时，大家最重要关心的就是程序所用算法在运行时所要花费的时间代价和程序中所使用的数据结构所占有的空间代价。③也就是说，通常用时间复杂度和空间复杂度来衡量一个算法的效率
  • 评估角度
    • 空间复杂度
    • 时间复杂度
      • 方法
        • 事前分析估算法
        • 事后统计法
      • 大小
        • O（1）＜O（log2n）＜O（n）＜O（nlog2n）O（n2）＜O（n3）＜O（2n）＜O（n！）O（nn）
      • 分类
        • 最坏时间复杂度
          • 最坏时间复杂度指在最坏情况下算法的时间复杂度。
        • 最好时间复杂度
          • 最好时间复杂度指在最好情况下算法的时间复杂度。
        • 平均时间复杂度
          • 平均时间复杂度指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
      • 题型
        • 加法原则
          • 适用于几个独立的for循环，彼此不嵌套
        • 乘法原则
          • 适合于一个for循环嵌套，且内外for循环次数彼此独立。
        • 首项加末项乘以项数除以二
          • 适合于一个for循环嵌套，但内外for循环次数彼此不独立有关联。
        • 保留最高次幂项原则
          • 适合于能直接看出循环次数，保留最高次幂项，并且去掉最高次幂项的系数。
        • 设未知量方法
          • ①设循环次数等于t。
          • ②通过列举前三五次循环变量与循环次数，找出t与i的关系。（这里的i指的是循环变量）
          • ③把通过②找到的t和i的这个等式代入循环条件中。
          • ④解出t的值。
          • ⑤表示出时间复杂度。（保留最高次幂项，并且去掉最高次幂项的系数。）