算法的概念
如果将最终写好运行的程序比作战场,我们码农便是指挥作战的将军,而我们所写的代码便是士兵和武器。数据结构和算法则是兵法。如果我们常看兵法,便可以做到胸有成竹,有时会事半功倍!同样,如果我们常看算法,我们写程序时也能游刃有余、明察秋毫,遇到问题时亦能入木三分、迎刃而解。对于算法而言,实现的语言并不重要,重要的是思想。算法可以有不同的语言描述实现版本(如C描述、C++描述、Python描述等等)
算法的五大特征
- 输入性:有零个或者多个外部量作为算法的输入
- 输出性:算法至少有一个量作为输出
- 确定性:算法的每条指令清晰,无歧义
- 有穷性:算法的每条指令的执行次数有限,执行每条指令时间也有限
- 可行性:算法原则上能够精确的运行,而且人们用纸和笔做有限次运算后就可完成
算法应用实际案例
【示例】如果a+b+c= 1000,且a^2 +b^2=c^2(a,b,c为自然数),如何求出所有a,b,c可能的组合:
没学算法前:三次暴力循环
1. import time 2. begin_time = time.time() 3. for a in range(0,1001): 4. for b in range(0,1001): 5. for c in range(0,1001): 6. if a+b+c == 1000 and a**2+b**2 == c**2: 7. print("a,b,c:",a,b,c) 8. end_time = time.time() 9. print("这段代码一共执行了:",end_time-begin_time,"s")
学过算法之后:通过abc关系直接生成c:
1. import time 2. begin_time = time.time() 3. for a in range(0,1001): 4. for b in range(0,1001): 5. c = 1000-a-b 6. if a+b+c == 1000 and a**2+b**2 == c**2: 7. print("a,b,c:",a,b,c) 8. end_time = time.time() 9. print("这段代码一共执行了:",end_time-begin_time,"s")
可以看到之前用暴力循环求解用时为260多秒,用第二种算法用时为1秒多,所用时间大大减少。
算法效率衡量标准
单靠时间值绝对可信吗?如果同一段程序放到不同配置上面的电脑去运行,其运行时间可能也会相差很多,但这是同一段程序,其效率是一定的。程序的运行离不开计算机环境包括硬件和操作系统,这些客观原因会影响程序运行的速度并反应在程序的执行时间山。那么如何才能客观的评判一个算法的优劣呢?
这就是后面要学习的时间复杂度和空间复杂度