月度存档: 一月 2019

主定理 与 时间复杂度

主定理最早出现在《算法导论》中,提供了分治方法带来的递归表达式的渐近复杂度分析。
规模为n的问题通过分治,得到a个规模为n/b的问题,每次递归带来的额外计算为c(n^d)
T(n) <= aT(n/b)+c(n^d)
那么就可以得到问题的复杂度为:

  • T(n) = O(n^d log(n)), if a = b^d

  • T(n) = O(n^d ), if a < b^d

  • T(n) = O(n^logb(a))), if a > b^d

二分搜索

  • 每次问题规模减半,a=1,b=2,c=0

  • 复杂度为n^0 O(log n)

二叉树遍历

    每次问题规模减半,a=2,b=2,c=0

    复杂度为n O(n)

快速排序

  • 随机选择待排序序列中的一个数字作为划分字问题的标准,划分是否平均影响算法复杂度

  • 每次问题规模减半,a=2,b=2,c=1

  • 复杂度为n^2 O(n log n)

  • 最差情况下,复杂度为O(n^2)

归并排序

  • 数据列均分为两部分,分别排序,之后以O(n)的复杂度进行合并,空间复杂度O(n)

  • 每次问题规模减半,a=2,b=2,c=1

  • 复杂度为n log(n)