有关于优化复杂度

发表于 | 分类于

有关于优化复杂度

时间复杂度 ：与代码的结构有非常强的关系。
经验论：
顺序结构 O(1)
二分查找 O(logn)
for循环 O(n)
顺序for循环 O(n)+O(n) 也是 O(n)
嵌套for循环 O(n^2)

空间复杂度 ： 与代码中的数据结构的选择高度相关

优化的终极目标： 尽可能低的时间复杂度和空间复杂度，去完成一段代码的开发。 一般都 以空间换时间，因为时间是无价的
常见降低时间复杂度方法： 递归，二分，排序算法，动态规划等
降低空间复杂度核心思路： 能用低复杂度的数据结构， 就不用高复杂度的数据结构

日常尽量使用 内置方法，一般是最优的，但面试还是最好用基本数据结构实现

查最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a = [1, 2, 3, 4, 9, 8, 7, 6, 5，5，4，5，9]

def max_value1():
    max_value = max(a)  # 内置 max() 函数
    print(max_value)


def max_value2():
    max_value = float('-inf')  # float('-inf'), float('inf')  无穷小 与 无穷大 
    for i in a:
        if i > max_value:
            max_value = i  
    print(max_value)

test1()
test2()

程序优化的核心思路：

  1. 暴力解法
  2. 剔除无效操作
  3. 时空转换，设计合理数据结构，完成时间复杂度向空间复杂度转移

示例

剔除无效操作

时间复杂度 O(n**3) 降低为 O(n**2)

1,2,5 三种金额组成 100 元，有多少种组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from timeit import Timer

## 暴力解法
def add100_1():
    sum = 0
    for i in range(0, 21):
        for j in range(0, 51):
            for k in range(0, 101):
                if 5*i + 2*j + k == 100:
                    sum += 1

## 剔除无效操作
def add100_2():
    sum = 0
    for i in range(0, 101):
        for j in range(0, 51):
            k = 100 - 1*i - 2*j
            if k == 0:
                sum += 1
            elif k > 0 and k % 5 ==0:
                sum += 1

## 进一步剔除无效操作， 随着 i 的增大， j 的循环次数会变小, 不过时间复杂度不变，扩展一下
def add100_3():
    sum = 0
    for i in range(0, 101):
        for j in range(0, (100 - i)//2 + 1):
            k = 100 - 1*i - 2*j
            if k == 0:
                sum += 1
            elif k > 0 and k % 5 ==0:
                sum += 1



t1 = Timer("add100_1()", "from __main__ import add100_1")
print("add100_1 cost ",t1.timeit(number=1000), "seconds")

t2 = Timer("add100_2()", "from __main__ import add100_2")
print("add100_2 cost ",t2.timeit(number=1000), "seconds")

t3 = Timer("add100_3()", "from __main__ import add100_3")
print("add100_3 cost ",t3.timeit(number=1000), "seconds")
'''
add100_1 cost  10.915886700000101 seconds
add100_2 cost  0.9650682000001325 seconds
add100_3 cost  0.5938704999998663 seconds

时空转换

时间复杂度 O(n**2) 降低为 O(n)

输入数组 a = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7], 查找出现最多的数值， 输出 5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
## 嵌套 for 循环  O(n\*\*2)
from timeit import Timer


def test1():
    a = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7]
    max_index = -1 
    time_max = 0 
    for i in range(len(a)): 
        time_tem = 0 
        for j in range(len(a)):   # 第二层循环  所有的 元素 与 a[i] 匹配
            if a[i] == a[j]: 
                time_tem +=1 
        if time_tem > time_max: 
            time_max = time_tem 
            max_index = a[i] 
    return (max_index, time_max)

## 使用字典结构，两个并行的 for 循环 O(n) + O(n) 还是  O(n)
def test2():
    a = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7]
    b = dict()
    for i in range(len(a)):  # 以元素值为 key, 次数为 value 生成字段的 键值对
        if a[i] in b:
            b[a[i]] += 1 
        else: 
            b[a[i]] = 1
    v_max = 0 
    k_max = 0
    for k, v in b.items():  # 查找最大的 value 以及对应的 key   
        if v > v_max:
            v_max = v
            k_max = k
    return (k_max, v_max)

    
        

t1 = Timer("test1()", "from __main__ import test1")
print("test1 cost ",t1.timeit(number=1000), "seconds")

t2 = Timer("test2()", "from __main__ import test2")
print("test2 cost ",t2.timeit(number=1000), "seconds")

'''
test1 cost  0.012685200000305485 seconds
test2 cost  0.0039678000002822955 seconds
'''