如何快速进行网站开发,网站怎么优化排名的方法,a站app下载,哪里有网站设计公司一、什么是算法分析程序和算法的区别#xff1a;算法是对问题解决的分步描述程序是采用某种编程语言实现的算法#xff0c;同一个算法通过不同的程序员采用不同的编程语言#xff0c;能产生很多程序算法分析的概念#xff1a;算法分析主要就是从计算资源消耗的角度来评判和…一、什么是算法分析程序和算法的区别算法是对问题解决的分步描述程序是采用某种编程语言实现的算法同一个算法通过不同的程序员采用不同的编程语言能产生很多程序算法分析的概念算法分析主要就是从计算资源消耗的角度来评判和比较算法更高效利用计算资源或者更少占用计算资源的算法就是好算法计算资源指标:一种是算法解决问题过程中需要的存储空间或内存另一种是算法的执行时间运行时间检测:1 #累计求和程序的运行时间检测2 #迭代法3 importtime45 defsum1(n):6 start time.time()7 theSum 08 for i in range(1,n1):9 theSum i10 end time.time()11 return theSum, end -start1213 for i in range(5):14 print(Sum is %d required %10.7f seconds%sum1(10000))n 10000 时执行5次的结果为Sum is 50005000 required 0.0000000secondsSumis 50005000 required 0.0009980secondsSumis 50005000 required 0.0000000secondsSumis 50005000 required 0.0000000secondsSumis 50005000 required 0.0009968 secondsn 100000 时, 执行5次的结果为Sum is 5000050000 required 0.0049877secondsSumis 5000050000 required 0.0049853secondsSumis 5000050000 required 0.0049860secondsSumis 5000050000 required 0.0049872secondsSumis 5000050000 required 0.0049863 secondsn 1000000时执行5次的结果为Sum is 500000500000 required 0.0528579secondsSumis 500000500000 required 0.0518231secondsSumis 500000500000 required 0.0528951secondsSumis 500000500000 required 0.0519009secondsSumis 500000500000 required 0.0527823 seconds1 #累计求和程序的运行时间检测2 #利用高斯求和公式的无迭代算法3 importtime45 defsum2(n):6 start time.time()7 theSum (n * (n1)) / 28 end time.time()9 return theSum, end -start1011 for i in range(5):12 print(Sum is %d required %10.7f seconds%sum2(10000))n 10000,100000,1000000时执行5次的结果时间均相同为0.0000000 seconds比较第一种迭代算法包含一个循环这个循环运行次数跟累加值n有关n增加循环次数也会增加第二种无迭代算法运行时间比第一种短很多运行时间与累计对象n的大小无关二、大O表示法算法时间度量指标一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标赋值语句是度量指标的一个合适选择一条赋值语句同时包含了(表达式)计算和(变量)存储两个基本资源数量级函数(Order of Magnitude)基本操作数量函数T(n)的精确值不是特别重要重要的是T(n)中起决定性因素的主导部分数量级函数描述了T(n)中随着n增加而增加速度最快的主导部分常见的大O数量级函数三、变位词判断问题1 #解法1逐字检查23 defanagramSolution1(s1, s2):4 alist list(s2)5 pos1 06 stillOK True7 while pos1 len(s1) andstillOK:8 pos2 09 found False10 while pos2 len(alist) and notfound:11 if s1[pos1] s2[pos2]:12 found True13 else:14 pos2 pos2 115 iffound:16 alist[pos2] None17 else:18 stillOK False19 pos1 pos1 120 returnstillOK2122 print(anagramSolution1(abcd,cabd))1 #解法2排序比较23 defanagramSolution2(s1, s2):4 alist1 list(s1)5 alist2 list(s2)67 alist1.sort()8 alist2.sort()9 pos 010 matches True11 while pos len(s1) andmatches:12 if alist1[pos] alist2[pos]:13 pos pos 114 else:15 matches False16 returnmatches1718 print(anagramSolution2(abcde,edcba))1 #解法4计数比较23 defanagramSolution4(s1, s2):4 c1 [0] * 265 c2 [0] * 266 for i ins1:7 pos ord(i) - ord(a)8 c1[pos] c1[pos] 19 for j ins2:10 pos ord(j) - ord(a)11 c2[pos] c2[pos] 112 k 013 stillOK True14 while k 26 andstillOK:15 if c1[k] c2[k]:16 k k 117 else:18 stillOK False19 returnstillOK2021 print(anagramSolution4(abcde,edcba))四、Python数据类型的性能1、列表list和字典dict的对比2、4种生成前n个整数列表的方法性能比较1 #4种生成前n个整数列表的方法性能比较2 from timeit importTimer34 deftest1():5 l []6 for i in range(1000):7 l l [i]89 deftest2():10 l []11 for i in range(1000):12 l.append(i)1314 deftest3():15 l [i for i in range(1000)]1617 deftest4():18 l list(range(1000))1920 t1 Timer(test1(),from __main__ import test1) #创建一个Timer对象,指定需要反复运行的语句和只需要运行一次的“安装语句”21 print(concat %f seconds\n % t1.timeit(number10000)) #调用Timer对象的timeit方法其中可以指定反复运行多少次2223 t2 Timer(test2(),from __main__ import test2)24 print(append %f seconds\n % t2.timeit(number10000))25 t3 Timer(test3(),from __main__ import test3)26 print(comprehension %f seconds\n % t3.timeit(number10000))27 t4 Timer(test4(),from __main__ import test4)28 print(list range %f seconds\n % t4.timeit(number10000))concat 14.517047secondsappend0.859504secondscomprehension0.517713secondslist range0.127913 seconds3、list.pop的计时试验#-*- coding: utf-8 -*-Created on Thu Oct 17 20:30:27 2019author: wu#list.pop的计时试验比较pop()和pop(0)两种方法from timeit importTimerimporttimeitimportnumpy as npimportmatplotlib.pyplot as pltpop0 timeit.Timer(x.pop(0),from __main__ import x)popend timeit.Timer(x.pop(),from __main__ import x)print(pop(0) pop())l1[]l2[]for i in range(1000000,10000001,100000):xlist(range(i))pt popend.timeit(number100)l1.append(pt)xlist(range(i))pz pop0.timeit(number100)l2.append(pz)print(%15.5f,%15.5f %(pz,pt))j np.arange(1000000,10000001,100000)plt.plot(j,l1,labelpop)plt.plot(j,l2,labelpop0)plt.xlabel(n)plt.ylabel(time(s))plt.legend()plt.show()4、list和dict的in操作对比1 #验证list中检索一个值以及dict中检索一个值的对比2 importtimeit3 importrandom4 importnumpy as np5 importmatplotlib.pyplot as plt67 l1,l2 [],[]8 n []9 for i in range(10000,1000001,20000):10 t timeit.Timer(random.randrange(%d) in x%i,from __main__ import random,x)11 x list(range(i))12 lst_time t.timeit(number100)13 l1.append(lst_time)14 x {j:None for j inrange(i)}15 d_time t.timeit(number100)16 l2.append(d_time)17 print({},{:10.3f},{:10.3f}.format(i,lst_time,d_time))1819 for i in range(10000,1000001,20000):20 n.append(i)2122 plt.plot(n,l1,go-,labellist)23 plt.plot(n,l2,r*-,labeldict)24 plt.xlabel(n)25 plt.ylabel(time)26 plt.legend()27 plt.show()28
