algorithms 时间复杂度

参考链接

• 数学公式

• CSDN.zolalad

python 数据结构时间复杂度

列表

集合

求差集 与 更新为差集的运算时间复杂度并不相同! 差集是生成新的集合, 更新为差集是将t中的元素从s移除, 因此可以根据是否需要新集合来选择合适方法

字典

实例分析

1. O(1)

• demo code

t = i
i = j
j = t

• 说明

  上述三条单个语句的频度均为1, 程序段的执行时间是与问题规模n无关的常数. 算法的时间复杂度为常数阶, 记作T(n) = O(1).

• 注意

  如果算法的执行时间不随着问题规模n的增加而增长, 即使算法中有上千条语句, 执行时间也不过一个较大的常数, 故此类算法的时间复杂度为O(1)

• 结论: $T(n) = O(1)$

2. O(n²)

$$
T(n) = O(n²)
$$

• demo code 1

sum = 0	# 1次
n = 100	# 1次
for i in range(n):	# n+1次
  for j in range(n):# n²次
    sum += 1		# n²次
    
# Θ(2n²+n+1)=n²（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)==O(n²)

• 解释

  Θ(2n²+n+1)=n²（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)==O(n²)

  • 结论: $\Theta(2n^2 + n + 1) = n^2 {\rightarrow}T(n) = O(n^2)$

• demo code 2

n = 100	# 1
for i in range(n): # n
  y += 1	# 1
  i += 1	# 1
  for j in range(2*n):	# (n-1)*(2n+1) => 2n² -n -1
    j += 1	# 1
    x += 1	# 1

• 说明

  一般情况下, 只需要考虑循环体中语句的执行次数, 忽略终值判别, 控制转移等, 当由若干循环语句时, 算法的时间复杂度是由嵌套导数最多的循环语句中最内层语句的频度f(n)决定的

3. O(n)

• demo code

a = 0	# 1
b = 1	# 1
n = 100	# 1
for i in range(n):	# n
  a, b = b, a	# 1
  i += 1	# 1

• 说明

$$
T(n) = 3 + n + 2(n - 1) = 3n + 1 = O(n)
$$

4. O($log_2n$)

• demo code

i = 1	# ①
while i < n:
  i = i * 2	# ②

• 说明

  语句1频度为1
  语句2为 f(n), 则 2^f(n) <= n; f(n) <= log~2~n
  取最大值 f(n)=log~2~n

• 结论: $T(n) = O(log_2n)$

5. O($n^3$)

• demo code

for i in range(n):
  i += 1
  for j in range(i):
    j += 1
    for k in range(j):
      k += 1
      x += 1

• 说明

  简单可以认为循环次数代表了时间复杂度 O(n³)