时间复杂度

时间复杂度

老师的课件

image-20211030203035060

我的理解

好像没有什么理解的了,就是课件上的内容

注意事项

  1. big O表示法是去掉低阶项,以及高阶项系数后的表示方法,而且反映的是该算法在最差情况下的复杂度
  2. big O 表示法不能反映出算法程序运行的具体时间,但是能够反映出算法程序与数据量之间的关系

讲解

会根据后面的例题进行讲解

等规模递归情况的时间复杂度(master公式)

如果递归的子问题是等规模的时候,算递归算法的时间复杂度可以直接套用master公式

假设递归的递推公式如下:

$$ T(n)=aT(\frac{n}{a})+O(n^d)$$则时间复杂度有三种情况:

  1. 如果$\log_ba<d$,则$T(n)=O(n^d)$
  2. 如果$\log_ba>d$ , 则$T(n)=O(n^{\log_ba})$
  3. 如果$\log_ba=d$ , 则$T(n)=O(n^{d}*\log{n})$
0%