算法001_时间复杂度

2023-12-17 本文已影响0人为宇绸缪

时间复杂度
算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模的 $n$ 的函数 $f(n)$ 。
算法的时间复杂性也因此记作 $T(n) = O(f(n))$ 。 $O$ 表示的是运行时间的上界。
因此，问题规模 $n$ 越大，算法执行的时间的增长率与 $f(n)$ 的增长率正相关，称作渐进时间复杂性。

时间复杂度类比
类比生活中的一些事件，估计时间

事件	时间
眨一下眼	一瞬间 / 几毫秒
口算 29 + 68	几秒
烧一壶水	几分钟
睡一觉	几小时
完成一个项目	几天 / 几星期 / 几小时
飞船从地球飞出太阳系	几年

代码分析时间复杂度
（1）代码1： $O(1)$

print("Hello World")

（2）代码2： $O(n)$

for i in range(n):
  print("Hello World")

（3）代码3： $O(n^2)$

for i in range(n):
  for j in range(n):
    print("Hello World")

（4）代码4： $O(n^3)$

for i in range(n):
  for j in range(n):
    for k in range(n):
      print("Hello World")

（5）代码5： $O(1)$
计算机当中打印这种基本操作，只要不上升到问题规模上，都是可以认为在一个时间单位内完成

print("Hello World")
print("Hello Python")
print("Hello Algorithm")

（6）代码6： $O(n^2)$
第一层 for 循环当中，由一个 print 和另外一个 for 循环。整体的复杂度相当于 $n * (n+1) = n^2 + n$ 。但是保留大单位即可，强调大概得运行时间，而不是精确的时间。比如人睡觉说自己睡了几个小时，而不会强调自己睡了7个小时零3分钟。

for i in range(n):
  print("Hello World1")
  for j in range(n):
    print("Hello World2")

（7）代码7： $O(log_2n)$ 或 $O(logn)$

while n > 1:
  print(n)
  n = n // 2

当 n = 64 的时候，输出的结果为 64、32、16、8、4、2。这种代码每次循环，问题规模就减少一半。
$2^6 = 64$ --> $log_264=6$
时间复杂度记为 $O(log_2n)$ 或 $O(logn)$
当算法过程出现循环折半的时候（问题规模减半的时候），复杂度式子中会出现 $logn$

时间复杂度-小结
（1）时间复杂度是用来估算算法运行时间的一个式子（单位）
（2）一般来说，时间复杂度高的算法比复杂度低的算法慢。和机器性能和问题规模有关
（3）常见的时间复杂度（按效率排序）
$O(1)$ < $O(logn)$ < $O(n)$ < $O(nlogn)$ < $O(n^2)$ < $O(n^2logn)$ < $O(n^3)$
（4）复杂问题的时间复杂度
$O(n!)$ 、 $O(2^n)$ 、 $O(n^n)$

快速判断时间复杂度

快速判断算法复杂度（适用于绝大多数简单情况）
- 确定问题规模 n（循环次数）
- 是否有循环减半过程 --> $logn$
- 有 k 层关于 n 的循环 --> $n^k$
复杂情况：根据算法执行过程判断

算法001_时间复杂度

猜你喜欢

热点阅读