理解常见的算法时间复杂度

1、常见的算法时间复杂度

# 常数阶 O(1)
n = 10

# 线性阶 O(n)
for i in range(n): print(i)

# 平方阶 O(n^2)
for i in range(n): for j in range(n): print(i + j)

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

2、对数阶 O(logN)

i = 1
while i <= n: i = i * 2 print(i)

  
 

  
1
  
2
  
3
  
4
 

理解

i*2之后，距离n越来越近

输出的i值：
2   4 8 16
2   2*2  2*2*2   2*2*2*2
2^1 2^2  2^3 2^4

假设需要执行x次，那么2^x = n
=> x = log_2(N) 
=> O(logN)

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

参考

1. 时间复杂度和空间复杂度的计算
2. 算法复杂度对数阶O（logn）详解
3. 对数阶 O(logn)

文章来源: pengshiyu.blog.csdn.net，作者：彭世瑜，版权归原作者所有，如需转载，请联系作者。

原文链接：pengshiyu.blog.csdn.net/article/details/107951165