python数据结构与算法

数据结构与算法(Python) Why?
我们举⼀个可能不太恰当的例⼦:
如果将开发程序的过程⽐喻为作战,我们码农便是指挥作战的将军,⽽我们 所写的代码便是⼠兵和武器。
那么数据结构和算法是什么?答⽈:兵法!
我们可以不看兵法在战场上⾁搏,如此,可能会胜利,可能会失败。即使胜 利,可能也会付出巨⼤的代价。我们写程序亦然:没有看过数据结构和算 法,有时⾯对问题可能会没有任何思路,不知如何下⼿去解决;⼤部分时间 可能解决了问题,可是对程序运⾏的效率和开销没有意识,性能低下;有时 会借助别⼈开发的利器暂时解决了问题,可是遇到性能瓶颈的时候,⼜不知 该如何进⾏针对性的优化。
如果我们常看兵法,便可做到胸有成⽵,有时会事半功倍!同样,如果我们 常看数据结构与算法,我们写程序时也能游刃有余、明察秋毫,遇到问题时 亦能⼊⽊三分、迎刃⽽解。
故,数据结构和算法是⼀名程序开发⼈员的必备基本功,不是⼀朝⼀夕就能 练成绝世⾼⼿的。冰冻三尺⾮⼀⽇之寒,需要我们平时不断的主动去学习积 累。
引⼊
先来看⼀道题:
如果        a+b+c=1000,且        a^2+b^2=c^2(a,b,c        为⾃然数),如何求出所有 a、b、c可能的组合?
第⼀次尝试

[AppleScript]纯文本查看__复制代码

?

1

2

3

4

import  time

start_time =   time.time`(`)

#   注意是三重循环 for a   in  range(0,    1001):              for b   in  range(0,    1001):                              for c   in  range(0,    1001):                                              if  a**2    +   b**2    ==  c**2    and a+b+c   ==  1000:                                                               print("a,   b,  c:  %d, %d, %d" %   (a, b,  c))

end_time =   time.time`()` `print("elapsed: %f"` `%` `(end_time -   start_time)) print("complete!"`)

运⾏结果:

[AppleScript]纯文本查看__复制代码

?

1

a`,  b,`  `c:  0,`  `500,    500 a,`  `b,  c:`  `200,    375,`    `425` `a,  b,`  `c:  375,`    `200,    425 a,`  `b,  c:`  `500,    0,`  `500` `elapsed:    214.5`83347 complete!

注意运⾏的时间:214.583347秒

算法的提出
算法的概念
算法是计算机处理信息的本质,因为计算机程序本质上是⼀个算法来告诉计 算机确切的步骤来执⾏⼀个指定的任务。⼀般地,当算法在处理信息时,会 从输⼊设备或数据的存储地址读取数据,把结果写⼊输出设备或某个存储地 址供以后再调⽤。
算法是独⽴存在的⼀种解决问题的⽅法和思想。
对于算法⽽⾔,实现的语⾔并不重要,重要的是思想。
算法可以有不同的语⾔描述实现版本(如C描述、C++描述、Python描述 等),我们现在是在⽤Python语⾔进⾏描述实现。
算法的五⼤特性
1.        输⼊:        算法具有0个或多个输⼊ 2.        输出:        算法⾄少有1个或多个输出 3.        有穷性:        算法在有限的步骤之后会⾃动结束⽽不会⽆限循环,并且每⼀个 步骤可以在可接受的时间内完成 4.        确定性:算法中的每⼀步都有确定的含义,不会出现⼆义性 5.        可⾏性:算法的每⼀步都是可⾏的,也就是说每⼀步都能够执⾏有限的 次数完成

第⼆次尝试

[AppleScript]纯文本查看__复制代码

?

1

2

3

4

import  time

start_time =   time.time`(`)

#   注意是两重循环 for a   in  range(0,    1001):              for b   in  range(0,    1001-a):                                c   =   1000    -   a   -   b                               if  a**2    +   b**2    ==  c**2:                                               print("a,   b,  c:  %d, %d, %d" %   (a, b,  c))[/size][/font]

[`font=微软雅黑][size=3]end_time` `=`   `time.time()` `print("elapsed: %f"` `%` `(end_time -   start_time)) print("complete!"`)

运⾏结果:

[AppleScript]纯文本查看__复制代码

?

1

a`,  b,`  `c:  0,`  `500,    500 a,`  `b,  c:`  `200,    375,`    `425` `a,  b,`  `c:  375,`    `200,    425 a,`  `b,  c:`  `500,    0,`  `500` `elapsed:    0.1`82897 complete!

注意运⾏的时间:0.182897秒

评论

暂无评论