枚举效率测试 --简单计算题

题目 :计算a+b+c=1000,a^2+b^2=c^2,求解a,b,c

要求:不适用数学模块计算

思路

装饰器

import time
def timer(f):
    def inner(*args,**kwargs):

        start_time=time.time()
        ret=f(*args,**kwargs)
        end_time=time.time()
        print("%s函数耗时>>>%s"%(f.__name__,end_time-start_time))
        return ret
    return inner

枚举法编程

@timer
def cul():
    #枚举效率太低:1001*1001*1001
    # 时间复杂度 T=1001*1001*1001*(1+max(1,0))
    result=[]
    for i in range(1001):
        for j in range(1001):
            for k in range(1001):
                if i+j+k==1000 and i*i+j*j==k*k:
                    result.append((i,j,k))
    print(result)

@timer
def cul2():
    #时间复杂度: T=1000*(1000-b)*(1+max(1,0))
    for i in range(1000):
        b=1000-i
        for j in range(b):
            c=1000-i-j
            if i*i+j*j==c*c:
                print(i,j,c)
cul()

cul2()

效率与结果演示

[(0, 500, 500), (200, 375, 425), (375, 200, 425), (500, 0, 500)]
cul函数耗时>>>116.00485754013062
0 500 500
200 375 425
375 200 425
500 0 500
cul2函数耗时>>>0.1517164707183838

时间复杂度:

cul : T=1001*1001*1001*2 --->T=2*n^3   ---> T=n^3  (n代表项目的复杂度)

cul: T=1000*2 ---> T=2*n  ----->T=n

时间复杂度计算原则

　　顺序结构：按照加法计算 (+)

　　条件结构：按照最坏时间复杂度计算max(O(x1),O(x2)...)

　　循环结构 ：按照乘法计算 (*)