Mdr-C-Tutorial

主题

时间复杂度 ​

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))。

可以更快速地用极限定义：

  1. f(n)∈Θ(g(n))⇔limn→∞f(n)g(n)=C
  2. f(n)∈O(g(n))⇔limn→∞f(n)g(n)=0 或 C
  3. f(n)∈Ω(g(n))⇔limn→∞f(n)g(n)=∞ 或 C
  4. f(n)∈o(g(n))⇔limn→∞f(n)g(n)=0
  5. f(n)∈ω(g(n))⇔limn→∞f(n)g(n)=∞

其中 C 是一个正常数。

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)

ln 的底数呢？

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

3. 空间复杂度 ​

1. 定义 ​

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

执行过程中

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

2. 表示方法 ​

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