Mdr-C-Tutorial

Appearance

时间复杂度 ​

经常有人疑惑 Θ(n)=lg⁡n 中 lg 的底数是多少；
对数的底数是几 无关紧要，因为根据 换底公式，不同底数的对数之间只差一个 常数，而计算时间复杂度的时候 不考虑 常数

1. 含义 ​

  1. 算法在特定输入下的 运行时间 指执行的基本操作数或步数
  2. 时间复杂度 是定性描述该算法运行时间的函数，可以用来估计该算法的运行时间
  3. 当输入规模足够大的时候，这个函数的低阶项和最高阶项的常数项对函数值的影响相较于最高阶项指数对函数值的影响来说可以 * 忽略不计*，也就是说只对运行时间的 次数 做描述

2. 渐进记号 ​

2.1. 定义 ​

  1. Θ(g(n))={f(n) | ∃ c1, c2, n0>0,∀ n≥n0, 0≤c1g(n)≤f(n)≤c2g(n)}
  2. O(g(n))={f(n) | ∃ c, n0>0,∀ n≥n0, 0≤f(n)≤cg(n)}
  3. Ω(g(n))={f(n) | ∃ c, n0>0,∀ n≥n0, 0≤cg(n)≤f(n)}
  4. o(g(n))={f(n) | ∀ c>0, ∃ n0>0, ∀n≥n0, 0≤f(n)<cg(n)}
  5. ω(g(n))={f(n) | ∀ c>0, ∃ n0>0, ∀n≥n0, 0≤cg(n)<f(n)}

注：规范的写法应当是 f(n)∈O(g(n))，但为了方便，可以用 f(n)=O(g(n)) 代替

2.2. 性质 ​

2.2.1. 传递性 ​

  1. f(n)=Θ(g(n))∧g(n)=Θ(h(n))⇒f(n)=Θ(h(n))
  2. f(n)=O(g(n))∧g(n)=O(h(n))⇒f(n)=O(h(n))
  3. f(n)=Ω(g(n))∧g(n)=Ω(h(n))⇒f(n)=Ω(h(n))
  4. f(n)=o(g(n))∧g(n)=o(h(n))⇒f(n)=o(h(n))
  5. f(n)=ω(g(n))∧g(n)=ω(h(n))⇒f(n)=ω(h(n))

2.2.2. 自反性 ​

  1. f(n)=Θ(f(n))
  2. f(n)=O(f(n))
  3. f(n)=Ω(f(n))

2.2.3. 对称性和转置对称性 ​

  1. f(n)=Θ(g(n))⇔g(n)=Θ(f(n))
  2. f(n)=O(g(n))⇔g(n)=Ω(f(n))
  3. f(n)=o(g(n))⇔g(n)=ω(f(n))

2.3 时间复杂度的表示 ​

  1. 时间复杂度可以用渐进记号表示，最常用的是大 O 记号
  2. 大多数情况下，我们只关注算法的最坏情况运行时间
    1. 对大部分算法来说，最坏情况经常出现
    2. 平均情况运行时间很可能等于最坏情况运行时间
    3. 有例外，比如快速排序

2.4 例子 ​

  1. 常数函数的时间复杂度是 Θ(1)，也可写成 Θ(n0)（为什么？）
  2. 函数的增长不一定能比较： f(n)=n，g(n)=n1+sin⁡n 此时 f(n)=O(g(n)) 和 f(n)=Ω(g(n)) 均不成立（为什么？）
  3. lg⁡(n!)=Θ(nlg⁡n)
    • 由 斯特林公式，lg⁡(n!)≈lg⁡(2πn(ne)n)=lg⁡(2πn)+nlg⁡(n)–nlg⁡(e)
      lg⁡(2πn) 和 −nlg⁡(e) 均可视为较 nlg⁡(n) 小的项
      ⟹lg⁡(n!)=O(nlg⁡n)。
    • 又因为 n!≥(n2)n2（为什么？）
      lg⁡(n!)≥n2lg⁡(n2)
      ⟹lg⁡(n!)≥c⋅nlg⁡n （其中c是某个常数）
      ⟹lg⁡n!=Ω(nlg⁡n)
    • 由以上两式子可得，lg⁡n!=Θ(nlg⁡n)

3. 空间复杂度 ​

1. 定义 ​

算法的 空间复杂度 指该算法 执行过程中 所需要消耗的存储空间资源

注：不要 把输入数据所占的存储空间包括在内

2. 表示方法 ​

与 时间复杂度 表示方法相同