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

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)

2、对数阶 O(logN)

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

理解

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. 算法复杂度对数阶O(logn)详解
  3. 对数阶 O(logn)
上一篇:Jquery的 each的使用 $.each()


下一篇:数据结构面试之十二——排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)