漫画算法:小灰的算法之旅学习 – 第1章 算法概述（时间复杂度？）

这是我参与更文挑战的第21天，活动详情查看： 更文挑战

• 紧跟上篇，这篇主要是时间复杂度及相关

时间复杂度

算法的好与坏

怎么衡量一个算法的好与坏?

• 衡量算法的好坏有很多标准,其中最重要的两大标准是算法的时间复杂度和空间复杂度。

• 基本操作执行次数
  • 场景1 T(n) = 3n，执行次数是线性的。
  • 场景2 T(n) = 5logn，执行次数是用对数计算的。
  • 场景3 T(n) = 2，执行次数是常量。
  • 场景4 T(n) = 0.5n2 + 0.5n，执行次数是用多项式计算的。

渐进时间复杂度

• 若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的 常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算 法的渐进时间复杂度，简称为时间复杂度。
• 因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法
• 直白地讲，时间复杂度就是把程序的相对执行时间函数,T(n)简化为一个数量级，这个数量级可以是n、n2、n3等

如何推导出时间复杂度呢?有如下几个原则。

• 如果运行时间是常数量级，则用常数1表示
• 只保留时间函数中的最高阶项
• 如果最高阶项存在，则省去最高阶项前面的系数

让我们回头看看刚才的4个场景。

• 场景1
  • T(n) = 3n， 最高阶项为3n，省去系数3，则转化的时间复杂度为:T(n)=O(n)。
• 场景2
  • T(n) = 5logn， 最高阶项为5logn，省去系数5，则转化的时间复杂度为:T(n) =O(logn)
• 场景3
  • T(n) = 2， 只有常数量级，则转化的时间复杂度为:T(n) =O(1)。
• 场景4
  • T(n) = 0.5n2+ 0.5n， 最高阶项为0.5n2，省去系数0.5，则转化的时间复杂度为:T(n) =O(n2)

以上最好的顺序是：O(1)<O(logn)<O(n)<O(n2)

时间复杂度的巨大差异