算法效率度量

算法效率度量方法

---

• 测量方法
  • 事后统计方法
    • 需要先编制好程序
  • 事前估算方法
    • 策略方案
    • 编译产生代码质量
    • 问题的输入规模
    • 机器执行指令的速度

---

• 分析算法运行时间
  • 不计循环索引的递增和循环终止条件等操作
  • 把基本操作和输入模式联系起来
  • 关注次数最高的项

---

• 时间复杂度
  • 定义大O计法
    • 问题规模记为$n$
    • 语句被执行的次数$T(n)$，即执行时间
    • 算法执行时间的增长率和$f(n)$的增长率相同表示为：$T(n) = O(f(n))$
    • $O()$被称为大O计法
  • 推导大O阶
    • 用常数1取代运行时间中的所有加法常数
    • 修改后的运行次数函数中，只保留最高阶
    • 如果最高阶项存在且不为1，则去除与这个项相乘的常数

---

术语	时间复杂度	例子
常数阶	$O(1)$	$2020$
线性阶	$O(n)$	$3n+4$
平方阶	$O(n^k)$	$3n^2+4n+5$
对数阶	$O(log(n))$	$3log(2)n+4$
nlogn阶	$O(nlogn)$	$2n+3nlog(2)n+14$
指数阶	$O(2^n)$	$2^n$

• 举例
  • $O(log(n))$

    int i = 1, n = 100;
    while( i < n )
    {
        i = i * 2;
    }

---

• 时间复杂度消耗时间从小到大依次为:$O(1)<O(logn)<(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

• $O(n^3)$之后基本不用考虑

---

• 算法空间复杂度
  • 算法运行所用空间