Day 1 数据结构与算法简介

Author: Denny Yu Created: January 19, 2022 9:48 AM Tags: 数据结构与算法

时间复杂度

解决同一个问题可以由多个算法，怎样衡量算法效率？

最直观：不同算法执行时间

时间值绝对是真实可靠的吗？

不一定,不同的PC有不同的计算速度

时间复杂度：

计算机需要执行的步骤数量来评价算法的效率

每台机器执行的总时间不容，但是执行基本运算数量大体相同

##枚举法一
for a in range(0,1001):
		for b in range(0,1001):
			for c in range(0,1001):
				if a+b+c==1000 and a**2+b**2==c**2:
					print({0},{1},{2}.format(a,b,c))
##时间复杂度T
T= 1000*1000*1000*2

##枚举法二
for a in range(0,1001):
		for b in range(0,1001):
			c=1000-a-b
			if a**2+b**2==c**2:
				print(a,b,c)
##时间复杂度T
T= 1000*1000*3

T=N*N*N...与N有关系

T ( n ) 1 = 2 n 3 , T ( n ) 2 = 3 n 2 T_{(n)1}=2n^3, T_{(n)2}=3n^2 T(n)1=2n3,T(n)2=3n2

大O记法：

比较T(n)的n的数量级，不关心系数，如上两种枚举算法 T n 1 = n 3 T_{n1}=n^3 Tn1=n3, T n 2 = n 2 T_{n2}=n^2 Tn2=n2,因此第二种算法运行效率要高于第一种，这样两种算法之间就可以比较简便地比较了，显然当n很小时，运行效率可能都差不多

最坏时间复杂度

最有时间复杂度，完成算法最少需要运行步骤的数量，反应最理想的情况 最坏时间复杂度，完成算法最多需要运行步骤的数量，在此程度的运算中，一定能完成计算工作 平均时间复杂度，完成算法平均需要运行步骤的数量

时间复杂度的几条基本规则

1. 基本操作，只有常数项，认为其时间复杂度为O(1)
2. 顺序结构，时间复杂度按加法进行计算
3. 条件语句，时间复杂度取最大值
4. 循环结构，时间复杂度按乘法进行计算
5. 如果没有特殊说明，时间复杂度通常指最坏时间复杂度

常见时间复杂度与大小关系

O(1) < O(logn) < O(n) < O(nlogn) < O( n 2 n^2 n2) < O( n 3 n^3 n3) < O( 2 n 2^n 2n) < O(n!) < O( n n n^n nn)

代码执行时间测量模块timeit

需要注意的是当函数体调用了其他函数，比如append()不能当作一个基本操作

class timeit.Timer(stmt=pass,setup=pass,timer=<timer function>)
## Timer是测量小段代码执行速度的类。

## stmt参数是要测试的代码语句（statment）；

## setup参数是运行代码时需要的设置；

## timer参数是一个定时器函数，与平台有关

测试不同方法构造列表的运行效率

import timeit
from timeit import Timer

def test1():
    l=[]
    for i in range(10000):
        l+=[i]

def test2():
    l=[]
    for i in range(10000):
        l.append(i)
    
def test3():
    l=[i for i in range(10000)]

def test4():
    l=list(range(10000))

timer1=Timer(stmt="test1()",setup="from __main__ import test1")
print("+:",timer1.timeit(1000))
timer2=Timer(stmt="test2()",setup="from __main__ import test2")
print("append:",timer2.timeit(1000))
timer3=Timer(stmt="test3()",setup="from __main__ import test3")
print("list comprehension:",timer3.timeit(1000))
timer4=Timer(stmt="test4()",setup="from __main__ import test4")
print("list(range()):",timer4.timeit(1000))
##输出
+: 0.6505592
append: 0.6184757
list comprehension: 0.2841973999999998
list(range()): 0.1617690999999999

List内置操作的时间复杂度

Dict内置操作的时间复杂度