python⾃学⽇记19——数据结构与算法（3）
python⾃学⽇记19——数据结构与算法(3)
linux查看文件夹有多少文件
算法分析
做算法分析前需要明⽩程序和它所代表的算法是不同的。算法是给定某个输⼊能得到对应的结果，是解决问题的⽅法，程序则是⽤某种编程语⾔对算法编码。同⼀个算法可以⽤python、java、C语⾔等各种编程语⾔写出来，即便在同⼀种语⾔中，⼀个算法也可以对应多个程序。
以前我对代码可读性并没有太多的感触，直到看到同⼀个算法⽤不同的程序写出来才明⽩代码可读性是那么的重要，下⾯是同⼀种算法计算前n个整数之和，算法的思路是使⽤⼀个初始值0的累加器变量，然后遍历n个整数，并将值加到累加器上：
程序1
def sumOfN(n):
theSum=0
for i in range(1,n+1):
theSum=theSum+i
return theSum
sumOfN(10)
数据可视化ui设计
程序2
def foo(tom):
fred=0
for bill in range(1,tom+1):
barney=bill
fred=fred+barney
return fred
foo(10)
前端面试项目中遇到的难点程序2的变量名和多余的赋值语句让这段程序代码很难读，不过两段代码从算法上考虑是⼀样的。
算法分析关⼼的是基于所使⽤的计算资源⽐较算法，追求更⾼的资源利⽤率和使⽤更少的资源。
计算资源：⼀是考虑算法解决问题占⽤的空间或内存，另⼀种是根据算法执⾏所需的时间进⾏分析和⽐较。
要通过执⾏时间对算法进⾏⽐较可以对算法进⾏基准测试，通过记录开始和结束时间差可以计算出每个算法所需要的时间。但是不同的计算机、程序、编译器、编程语⾔都会影响算法的执⾏时间，所以我们需要到⼀个不受这些影响的⽐较指标，这样才能更好的⽐较不同实现下的算法优劣。
⼤O表⽰法
以前了解过⼤O表⽰法，知道⼤概的意思，但是有些细节并不了解，具体是选定了什么指标具体怎么计算出来的也有点云⾥雾⾥的，这次对⼤O表⽰法有了更深⼊的了解。
⾸先，算法的时间度量指标是什么，仔细观察程序设计语⾔特性，除了与计算资源⽆关的定义语句外，主要就是三种控制流语句（顺序、分⽀判断、循环）和赋值语句，⽽控制流语句仅仅起到了组织语句的作⽤，并不实时处理。赋值语句同时包含了（表达式）计算和（变量）存储两个基本资源，所以赋值语句是⼀个合适的选择。
选定了度量指标然后对于前⾯的累加算法计算总和所⽤的赋值语句的数⽬。赋值语句是1（theSum=0)加上n(theSum=theSum+i的运⾏次数)。可以将其定义为T，令T(n)=1+n。从T(n)可以看出，影响算法执⾏时间的主要因素是n，我们将其称为问题规模。这样⼀来就可以说处理1000000个整数的问题规模⽐处理1000个整数的问题规模⼤，所以前者话的时间⽐后者花的时间长。算法分析的⽬标就是要出问题规模会怎么影响⼀个算法的执⾏时间。
从T(n)=1+n来看，随着n不断增加，1对算法的执⾏时间起的作⽤越来越⼩，也就是说T(n)函数中某⼀部分⽐其余部分增长得更快，为了⽅便⽐较，我们只需要⽐较这起决定性的部分就可以了。然后引出了⼀个数量级函数的感念，也被称为⼤O记法（O是指order），记作
O(f(n))，也就是记录步骤数的近似⽅法。所以T(n)可以直接舍去1，直接说执⾏时间是O(n).
关于⼤O还有⼀个重要的内容需要知道的是如何将⼀段程序⽤⼤O表⽰法记录步骤。
下⾯给出⼀个例⼦：
a =5
b =6
python基础知识测试题c =10    #三条赋值语句：3
部署图的组成包括
for  i in  range (n ):
for  j in  range (n ):  #两个循环都是n ，因为是嵌套循环是n**2
x =i *i
y =i *j
z =j *j #循环⾥有3条赋值语句所以是3*n**2
for  k in  range (n ):
w =a *k +45#两条赋值语句在⼀个n 循环⾥，所以是2n
v =b *bcontract什么意思
d =33 #⼀条赋值语句；1
根据上⾯的内容看出：
很容易看出随着n增加，n的平⽅起主导作⽤，所以这段代码的时间复杂度是
python 数据结构的性能
在实现列表、字典数据结构时，python设计师考虑将最常见操作变得⾮常快，也就是让最常⽤的操作性能最好，牺牲不太常⽤的法则。列表最常⽤的是：按索引取值和赋值，另⼀个常见的操作是加长列表，这些的⼤O效率是O(1)，也就是常数阶。加长列表有两种⽅式，要么采⽤追加，要么采⽤连接擦欧洲哦。追加⽅式是常数阶，如果待连接列表长度为k，那么连接操作的时间复杂度是O(k)。
字典的取值操作和赋值操作是常数阶，另⼀个重要的字典操作就是包含（检查某个键是否在字典中）也是常数阶。删除某个键值对也是常数阶。
1.证明列表的索引操作为常数阶
证明列表索引为常数阶需要计算时间，另外就是当列表的元素个数增加时查询具体索引的时间基本不变。
这⾥需要使⽤内置模块timeit，timeit模块会统计多次执⾏语句要⽤多久，默认会执⾏100万次，并在完成后返回⼀个浮点数格式的秒数。⾸先创建⼀个Timer对象，其参数是两条python语句，第⼀个参数是要统计时间的python语句，第⼆个是建⽴测试的语句。
from  timeit import  Timer
t1=Timer ('x[200]','from __main__ import x')
for  i in  range (100000,1000001,100000):
x =list (range (i ))
pt =t1.timeit (number =1000)#默认100万可以通过number 修改外1000次
print ('%.5f'%pt )#%.5f 保留5位⼩数
在循环10万到100万，每次增长10万，也就是循环10次，每次统计所需时间，最后都是0.00006秒。这⾥有⼏点需要说⼀下，Timer第⼆个参数测试语句可能会感觉有些奇怪，学过python基础可能都知道from和import，但是本例中’from __main__ import x '可能就是第⼀次见了。这个是为了将x从__main__命名空间导⼊到timeit设置计时的命名空间。这么做是为了在⼀个⼲净的环境中运⾏测试，⼀⾯某些变量以某种意外的⽅式⼲扰函数的性能。
刚开始写的时候也是出错好⼏次，遇到新模块时就会⾃乱阵脚将⾃⼰学过的⼀时忘掉了，为什么结果没循环，t1=Timer()是不是该放到循环⾥，也是尝试了好⼏次才成功的。这⾥需要记住的就是接触新知识点时不要乱了分⼨把过去学过的也忘了，把握住学过的再结合新的知识才是更好的学习⽅法。T (n )=3+3n +22n +1=3n +22n +4
O (n )
2

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。