时间复杂度例题

发表于 | 更新于 | 分类于 | 阅读次数：

介绍

可理解为程序运行步骤,主要看每一步需要运行的次数

大O表示法表明忽略常数项,只保留最核心,最特征的部分,忽略常量,低阶,系数

例题1
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
a + b + c = 1000 and a**2 + b**2 = c**2  
假设使用穷举法(枚举法),三层循环循环a,b,c的所有可能,加上两个if判断条件 得到时间复杂读1000*1000*1000*2
若 a + b + c = 2000,则时间复杂度为 2000*2000*2000*2 
若 a + b + c = N ,则时间复杂度为 N*N*N*2 O(n**3)
解:
for a in range(0, n):
    (循环用乘法计算)
    这句代码的运行步骤是:O(n)
 
for b in range(0, n):
    (循环用乘法计算)
    这句代码的运行步骤是:O(n)
 
c = n - a -b
    (基本操作语句为1)
    运行步骤为:O(1)
 
if a ^ 2 + b ^ 2 = c ^ 2:
print(a,b,c)
进入判断语句, 有两个分支
(当碰到分支语句的时候,取分支步骤最多的)
    分支1执行print(a,b,c)
        步骤为1
    分支2是判断条件失败,直接跳过了
        步骤为0
假设令c = N - a - b,使用双层循环,则时间复杂读为N*N *(1+max(0,1))   O(n**2)

######例题2

1
2
3
4
阅读电话簿中每个人的电话号码O(n)
在电话簿中根据电话号码找人O(n)
阅读电话簿中的以a开头的人的电话号码 O(n)
在电话里簿中根据名字查找电话号码  O(logn)

学习思路

1
Python数据结构与算法---->机器学习和深度学习和数据挖掘---->大数据----->NLP自然语言处理------->linux-------->数据库底层------->其他底层知识