• 算法： 指解决问题的一种方式或一个过程，算法是若干指令的有穷序列。

  • 满足性质： 输入、输出、确定性、有限性。

  • 程序与算法之间的联系： 程序是算法用某种程序设计语言的具体实现。

  • 计算机的两大资源： 时间、空间。

  • 常用提升算法的效率的方式： 牺牲空间换时间。

    • 问题求解的逻辑过程：
      1. 建模：对输入参数和解给出形式化或半形式化的描述。
      2. 设计算法： 采用什么算法设计技术，正确——是否对所有的实例都得到正确的解。
      3. 分析算法： ——效率

  • 常见排序算法的效率：

  • 算法时间复杂度： 针对指定基本运算，计数算法所做的运算次数。

    • 最坏情况下的时间复杂度：W(n);
    • 平均情况下的时间复杂度 ：A(n);

  • 平均情况下的时间估计（顺序检索法）：

  • 函数的渐近的界：

  • 相应定理：

    • 同阶：
    • 低阶：
    • 高阶：

  • 阶的高低：

  • 函数取整： ⌊X⌋ 向下取整，⌈x⌉ 向上取整；

  • 主定理的应用：

  • 公式：T(n)= aT(n/b)+f(n)

    • a:归约后的子问题的个数
    • n/b: 归约后子问题的规模
    • f(n)：归约过程及组合子问题的解的工作量

  • 共有三种情况：此处省略；

  • 常见的主定理

  • 二分检索： T(n)= T(n/2)+1

  • 二分归并排序： T(n)= 2T(n/2)+n-1

  • 例：

  • T(n)= 9T(n/3)+n

  • a = 9

  • b = 3

  • f(n) = n

T(n) = O（n^2）

更多推荐

算法入门基础知识总结