算法和数据结构引入

#如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?
‘‘‘
import time

start_time = time.time()

for a in range(0,501):
    for b in range(0,501):
        for c in range(0,501):
            if a+b+c==500 and a**2+b**2==c**2:
                print("a,b,c:%d,%d,%d"%(a,b,c))

end_time = time.time()
print("time:%d"%(end_time-start_time))
print("finish")
‘‘‘               

‘‘‘
每台机器执行的总时间不同，但是执行的基本运算数量大体相同
下面我们计算一下以上代码所执行的运算数量

时间复杂度：用运算的步骤数去衡量
T=500*500*500*2
如果用上面的方法计算a+b+c=n   n代表咱们解决问题的规模问题
则：T=n*n*n*2

T(n)=n^3*2
T(n)=n^3*k
k是与n无关的系数，并不影响整个函数n^3的走势，所以咱们可以忽略
所以可写成 T(n)=k*g(n)
g（n）=n^3  这个g函数叫做上面T函数的渐进函数，T（n）=O(g(n))故g函数也叫作一个时间复杂度的大O表示法
‘‘‘


#上面代码运行时间长62s，改一下,0s
import time

start_time = time.time()

for a in range(0,501):
    for b in range(0,501):
        c = 500-a-b
        if a**2+b**2==c**2:
             print("a,b,c:%d,%d,%d"%(a,b,c))

end_time = time.time()
print("time:%d"%(end_time-start_time))
print("finish")


‘‘‘
这段代码的时间复杂度为：
T(n)=n*n*(1+max(1,0))
    =n^2*2
    =O(n^2)
‘‘‘

#各种list生成方法    list不能算做基本运算，而是python给我们封装好的东西
‘‘‘
li1 = [1,2]
li2 = [3,4]

li = li1+li2     #加操作  实际上是吧li1和li2里的内容拿出来放在一个新列表中，然后让li指向这个新的列表

li = [i for i in range(1000)]        #列表生成器

li = list(range(1000))  #可迭代对象直接转换成列表，Pyhon2中无需转换，就是列表

li = []
for i in range(1000):
    li.append(i)            #往空列表中追加

li = []
for i in range(1000):
    li.extend([i])
‘‘‘

from timeit import Timer

def test1():
    li = []
    for i in range(1000):
        li.append(i)

def test2():
    li = []
    for i in range(1000):
        li+=[i]

def test3():
    li = list(range(1000))

def test4():
    li = [i for i in range(1000)]

timer1 = Timer("test1()","from __main__ import test1")  #这个测试时跑到另一个地方进行，找到test1()这个函数不能导入“算法引入2list.py”这个名字，而是用__main__代替
print("append:",timer1.timeit(1000))  #打印加操作花费的时间，测1000次

timer1 = Timer("test2()","from __main__ import test2")
print("+:",timer1.timeit(1000))

timer1 = Timer("test3()","from __main__ import test3")
print("list(range()):",timer1.timeit(1000))

timer1 = Timer("test4()","from __main__ import test4")
print("[i for i in range()]:",timer1.timeit(1000))

def test5():
    li = []
    for i in range(1000):
        li.insert(0,i)          #append是在末尾添加，这个insert参数的0代表总是在开头添加