时间复杂度

  • 常数操作： 与数据量没有关系的操作（+-*/和位运算）

根据常数操作数量的表达式，保留最高次，去掉系数，就是时间复杂度

用O（..）表示，时间复杂度越小越好，如果相同，就–实际去跑区分常数项时间

时间复杂度较差，是因为他运用了太多的时间比较行为，比较行为的效率不高，浪费了大量的比较行为才搞定某一个数

  • 额外空间复杂度

    如果是有限的变量来处理就可以完成算法，就是o(1)，如果是需要重新开辟一个数组来完成算法，就是o(n)

  • 递归的时间复杂度计算

master 公式 （子问题规模需要一样）

T（N） = a * T(N/b) + O(N^d)

T(N)指的是母问题的数据量是N级别的

T（N/b）子问题都是（N/b）规模，即每次调用子问题的规模都是一样的

a表示子问题的生成数量

O（N^d）除去调用之外的时间复杂度

如果符合master公式，可以推出下面式子

log ( b , a ) < d 时间复杂度为 O(N^d)

log ( b , a) > d 时间复杂度为 O(N^log(b,a))

log ( b, a) = d 时间复杂度为O(N^d * logN)