如何理解时间复杂度
Seaman Lv1

官方定义如下,若存在函数 $f(n)$ ,n 趋近于无穷大时,$T(n)/f(n)$ 的极限值为不等于零的常数,则称 $f(n)$是 $T(n)$的同数量级函数,记作 $T(n) = O(f(n))$,称为 $O(f(n))$,O 为算法的渐进时间复杂度,简称为时间复杂度。

这个定义看起来是晦涩难懂的,换一种直白的说法,时间复杂度就是程序运行,需要多少的时间。而程序运行需要多少时间,与程序运行的次数有不可分割的关系。程序运行的次数,我们可以把它称作基本操作次数,记作 $T(n)$。

不同量级的基本操作次数,时间复杂度(运行的时间)当然不同。这是一个因果关系,我们需要根据基本操作次数,得到时间复杂度。接下来我会举例说明常见的时间复杂度。在这之前请你记住三个获取时间复杂度的推导过程原则:

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

  • $O(1)$

假如现在我给你一个苹果和一根香蕉,你每 3 分钟可以吃掉一个苹果,那么吃掉一个苹果需要多久?当然是 3 分钟了,如果有 n 个香蕉呢?无论有多少的香蕉,吃掉苹果的时间都是 3 分钟,记作 $T(n) = 3$,根据时间复杂度推导过程原则,只有常数量级,时间复杂度转化为 $T(n) = O(1)$
image.png

  • $O(n)$

假如现在你是一名教师,批改完试卷后,你需要知道谁这次考的最差,给他一定的鼓励。那么你需要一张一张的去翻看试卷的分数。假如有 n 份试卷,查看一张试卷你需要 3 S,n 张试卷需要的时间是 3 x n,用函数表示 $T(n) = 3n$,根据时间复杂度推导过程原则,如果最高阶项存在,则省去最高阶项前面的系数,时间复杂度为 $T(n) = O(n)$

image.png

  • $O(n^2)$

还是翻试卷,照最低分的例子,不过这一次,你找到最低分的试卷后,把这张试卷单独拿出来放在一边,用同样的方法再去找倒数第二,再把它单独拿出来放在一边 … … 这样重复做了 n 次,每次的时间复杂度都是 $O(n)$,那么 n 次自然就是 $O(n^2)$
image.png

  • $O(logn)$

假如有 32 份试卷,你丢一次,还剩 16 份,丢两次,还剩下 8 份,丢三次,就只剩下 4 份了,可以这么一直丢下去,丢到第五次,就只剩下一份了。则 $log_2(32) = 5$,如果有 n 份,显然我们就有:
$$\frac{n}{2^k} => 1 => log_2n$$
大约需要 $log_2n$ 次,才能得到“找到”或者“没找到”的结果,根据时间复杂度推导过程原则,如果最高阶项存在,则省去最高阶项前面的系数,时间复杂度转化为 $O(logn)$
image.png

参考

  • Post title:如何理解时间复杂度
  • Post author:Seaman
  • Create time:2021-05-20 02:56:47
  • Post link:https://gongguowei.com/2021/05/20/time-complexity/
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments