复杂度分析


复杂度分析

渐进符号

形式化地,记 ,则

理解一下这些怪米日眼的式子:

,那么我们能找到两个正数 使得 ,感性地理解就是能被夹在中间。

符号相当于规定了上下界,而如果只有渐进上界的化则可以使用大 符号。 当且仅当 ,使得 ,感性理解就是 的某倍是 的上界。

符号是渐进上界,大 符号相当于就是渐进下界。 当且仅当 ,使得

而至于剩下的 ,可以把 理解为阶的小于等于号, 就是小于号; 是大于等于号, 就是大于号。

img

(图源算导,摘自 OI-Wiki,个人认为很能帮助人理解)

等价的定义:

  • 同阶函数集合
  • 低阶函数集合
  • 高阶函数集合
  • 严格低阶函数集合
  • 严格高阶函数集合

结合上述定义理解,不难发现一般使用 来分析算法时间复杂度的理由了:我们一般只关心最坏的上界而无所谓下界,但当然如果使用 的话会更严谨。

主定理 (Master Theorem)

使用 Master Theorem 来求解递归算法的复杂度。一般的,假设有如下递推关系式:

简证:

代入 ,则

其中

剩余证明咕了,不会。

看几个例子:

  • 归并排序运行时间的递归式:

    使用主定理求解,发现 ,所以

  • 另一个例子

    此处 ,其中 ,所以

 


最后修改日期:2021年1月26日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。