时间复杂度

什么是时间复杂度

• 时间复杂度是指程序执行的次数，可以用大写的字母O(次数)来表示，我们常见的时间复杂度可分为四种
  • 常数：程序执行次数是固定值
  • 线性：程序执行次数是n次
  • 对数：程序执行次数是折半的可以记为log以2为底n的对数
  • 高阶：程序执行次数为循环n次

为什么使用时间复杂度

• 用于判断算法的优劣，空间复杂度 相同时算法所执行的时间越小，算法越优。

常见的时间复杂度种类

• 一般我们所说的时间复杂度不是指具体的程序执行次数，而是假设程序执行的次数无穷大时的时间复杂度。
  • 常数：T(n)=O(1)
  • 线性：T(n)=O(n)
  • 对数：T(n)=O(log以2为底n的对数)
  • 高阶：T(n)=O(n的整数次方) 只有常数量级，时间复杂度转化为1。含有最高阶项则省略最高阶项前的系数。如果是多项式则只保留最高阶项。