当前课程知识点：基于Linux的C++ > 第四讲 算法 > 4.2 算法概念与特征 > LinuxCPP0402
首先来看算法的概念与特征
算法的基本概念
其实在第一讲的时候已经谈到过了
什么叫算法呀
算法就是解决的问题方法和步骤
有一个问题放在那个地方
编程实现它
编程实现的时候
你要给出解决问题的方法和步骤
第一步应该做什么
第二步应该做什么
第三步应该做什么
把它描述清楚了就叫算法
对于编程来讲
要不仅仅给出算法的步骤
最终还要编程实现
从算法的特征角度来讲
算法实际上包括了五个基本特征
第一个叫有穷性
算法在任何一种情况下边
都可以在有限步内终止
是一个非常重要的要求
第二个叫确定性
算法的每一个步骤
都必须要有一个明确的意义
它不能够有二义性
这是算法的确定性
第三个叫输入
算法可以有0个或多个输入
一个算法有输入当然没有问题
比如Add函数
一个算法也可以没有输入
如果所有的数据都是隐含的
已经存在了 比如九九乘法表
九九乘法表里面只不过是打印1乘9
2乘9、3乘9、一直到9乘9它们的积
用一个二维的表格打印出来
所有的细节信息都已经隐含了
所以不需要输入一系列的数据
但是不管怎么样
这个算法一定是要有输出的
必须带回来一个结果
你写了一个程序最终的目的
是为了产生一个新的信息
可能就会有辩论 我前面写了函数
返回值是一个void
它的输出体现在当它事情做完了以后
计算机内部的状态发生了变化
比如讲Swap函数
x和y两个形式参数的值发生了变化啊
这个就是输出 隐含着了
并没有在函数的返回值里面体现出来
第五个叫有效性
算法中的所有的操作
都具有明确的意义
并且能够在有限的时间内完成
有穷性表示步骤是有限的
有效性表示时间是有限的
你说如果我要给它一个期限的话
我希望是一万年 你别觉得很长
写了一个程序
跑一万年才能出来一个结果
这是长得受不了
一秒钟、两秒种结果就出来了
这样的程序能够忍受
如果程序慢了 一分钟才能出来结果
在那个地方等啊等就已经不耐烦了
但如果要一万年才能出来结果
那黄花菜都凉了
事实上 压根都不是这么一种情况
因为有一些算法比如讲一个解密算法
如果没有找到一个很好的解决方案
只能穷举 一个接着一个地去做
当密码很复杂的时候 暴力去破解
最后一万年压根都解决不了问题
弄不好得要地球都毁灭了
几十亿年才能够把问题解决掉
这样的算法是无效的
算法一定要在有限的时间内能够完成
同学们要特别记住
正确性是必须要通过数学去证明的
写了一个算法 得证明算法是正确的
如果你不知道怎么证明
那么你就必须测试你的程序
测试 你的程序是正确的 这样才行
简单的算法
正确性实际上是不言自明的
有的时候没有办法证明的话怎么办呢
只能去测试
还有一种算法就完全不一样了
没有正确性的证明算法你压根就写不出来
好多科学家啊
最后为了实现很有效的算法
为此都得发好多篇论文才能够写出代码
有了这些定理之后
才能够完成算法的设计
看一个例子 弄一个3乘3的幻方
想法其实也蛮简单的
要把9个整数放在3乘3的九宫格里
然后让它横、竖、斜线
最后和是相同的 都是15
这个幻方啊 如果同学们看金庸同志写的
《射雕英雄传》你就记得了
黄蓉就解决了这个问题
当年是有个口诀的 我们这是机械的
你必须给我一个
解决问题的步骤和一个逻辑来
那么逻辑是什么 这就给了你提示
1放在第一行的正中间
这就是我们的算法
你看看它怎么实现
2写在1的右肩
你写上去 就超出了幻方的范围
然后把它平移下来
最右下角3写在2的右肩
又超出范围了 平移
三个数写完了
把4写在3的下面
5写在4的右肩
6写在5的右肩
又3个数写完了
把7写在6的下边
把8写在7的右肩 平移
9写在8的右肩 平移
这是3乘3的幻方
刚才描述是不是很有规律
找到这样的规律就可以编程序实现
这就是幻方的填充步骤
步骤1应该干什么
步骤2干什么 步骤3干什么
很明确地用文字把它写出来
就这样完成了
第二例子来看查英文单词
英语字典和汉语字典不一样
汉语字典有很丰富的索引
有拼音索引 有笔画索引 偏旁部首索引
以前的字典还有四角号码索引
很容易去找
可是英语字典就是一个顺序的排列
这个排列称为辞典序
怎么查英文单词呢
翻开辞典任意一页去找
看要找那个单词
是不是在第一个单词的前边
如果是在前边 说明翻多了 再翻前面去
然后比较单词是不是在
那一页最后一个单词的后面
如果在后面 说明翻少了 朝后再继续翻
如果单词在这一页的第一个单词
和最后一个单词的中间
那我们就要从第一个单词
到最后一个单词一个一个去比较它
看看是我们所要的
找着了那就是我们找到了这个单词
找不着就说明
这个字典没包括这个单词
或者这个单词压根就不存在
这个就是我们查英文单词的过程
同学们仔细思考一下这个逻辑
你看是不是满足算法特征
那肯定是满足的
有穷性、确定性、输入、输出、有效性
不都是完全满足吗
那么它同样就是一个算法
但是在这个地方
我要特别跟同学们说一下
就是如果你真地这样查单词
这个效率是不会高的
那问题在哪里
就是你翻开词典任意一页的动作
最快速的动作应该折半
在C++的编程语言里面这样的查找方式
我们称它为Binary Search 叫折半查找
我有一个词典放在这个地方
我“咔”从中间分
单词在前半部分呢 后半部分呢
如果在前半部分那不就意味着
整个后半部分全部都砍掉了吗
然后在前半部分呢
如法炮制啊 再砍一半
看在前半部分呢 后半部分呢
每次我都能够扔掉内容的一半
这样的话查找效率是非常非常高的
因为每次都扔一半
下次扔一半的一半
再下次保留一半的一半的一半
三次下去就变成八分之一了呀
所以实际上它是一个以对数的形式
迅速递减的查找方式
这是log以2为底的计算
这就叫折半查找
可能很多同学就会说啊
那我真实翻字典的时候
压根就不是这么干的
为啥啊 比如说我要查一个单词
它是以A开头的
比如说深渊Abyss
查这个单词 Abyss
它是以字母A开头
字典1000多页让你砍了一半
最后在500、600页去找
那符合逻辑吗 你肯定脑子里面一转
这压根就不对
怎么字母A会在那个地方呢
不可能啊
肯定是在头百十来页那个位置嘛
你会砍一半在500、600页去找吗 不会的
你立即就会在50、60页前面翻
这个是你的智力的启发式
编程的时候除非你使用了启发式
否则这个事情是做不了的
它不像你的头脑中可以做到这件事
我们编程机械语言
不是那么容易做到的
我们能够做到的最快的那种方案
就是折半 除非你启发式
你一开始就说了
A在哪一个附近 B在哪一个附近
C在哪一个附近
完全告诉它 这样一种情况
既然首字母是A
那直接去查A那一部分就完了
B以后部分全砍掉
这就叫启发式了
你的算法可以这么设计
但是如果没有它
折半查找效率是最快的
-1.1 提纲
-1.2 程序设计的基本概念
-1.3 简单C/C++程序介绍
-1.4 程序设计的基本流程
-1.5 基本语法元素
-1.6 程序设计风格
-1.7 编程实践
-第一讲 C/C++基本语法元素--编程实践提交入口
-2.1 提纲
-2.2 结构化程序设计基础
-2.3 布尔数据
-2.4 分支结构
-2.5 break语句
-2.6 循环结构
-2.7 编程实践
-第二讲 程序控制结构--编程实践提交入口
-3.1 提纲
-3.2 函数声明、调用与定义
-3.3 函数调用栈框架
-3.4 编程实践
-第三讲 函数--编程实践提交入口
-4.1 提纲
-4.2 算法概念与特征
-4.3 算法描述
-4.4 算法设计与实现
-4.5 递归算法（一）
-4.6 递归算法（二）
-4.7 容错与计算复杂度
-4.8 编程实践
-第四讲 算法--编程实践提交入口
-5.1 提纲
-5.2 库与接口
-5.3 随机数库（一）
-5.4 随机数库（二）
-5.5 作用域与生存期
-5.6 典型软件开发流程（一）
-5.7 典型软件开发流程（二）
-5.8 编程实践
-第五讲 程序组织与开发方法--编程实践提交入口
-6.1 提纲
-6.2 字符
-6.3 数组（一）
-6.4 数组（二）
-6.5 结构体
-6.6 编程实践
-第六讲 复合数据类型--编程实践提交入口
-7.1 提纲
-7.2 指针基本概念
-7.3 指针与函数
-7.4 指针与复合数据类型（一）
-7.5 指针与复合数据类型（二）
-7.6 字符串
-7.7 动态存储管理（一）
-7.8 动态存储管理（二）
-7.9 引用
-7.10 编程实践
-第七讲 指针与引用--编程实践提交入口
-8.1 提纲
-8.2 数据抽象（一）
-8.3 数据抽象（二）
-8.4 链表（一）
-8.5 链表（二）
-8.6 链表（三）
-8.7 链表（四）
-8.8 函数指针（一）
-8.9 函数指针（二）
-8.10 抽象链表（一）
-8.11 抽象链表（二）
-8.12 编程实践
-第八讲 链表与程序抽象--编程实践提交入口
-9.1 提纲
-9.2 程序抽象与面向对象
-9.3 类类型
-9.4 对象（一）
-9.5 对象（二）
-9.6 类与对象的成员（一）
-9.7 类与对象的成员（二）
-9.8 类与对象的成员（三）
-9.9 继承（一）
-9.10 继承（二）
-9.11 继承（三）
-9.12 多态（一）
-9.13 多态（二）
-9.14 编程实践
-第九讲 类与对象--编程实践提交入口
-10.1 提纲
-10.2 四则运算符重载（一）
-10.3 四则运算符重载（二）
-10.4 关系与下标操作符重载
-10.5 赋值操作符重载（一）
-10.6 赋值操作符重载（二）
-10.7 赋值操作符重载（三）
-10.8 赋值操作符重载（四）
-10.9 赋值操作符重载（五）
-10.10 流操作符重载（一）
-10.11 流操作符重载（二）
-10.12 流操作符重载（三）
-10.13 操作符重载总结
-10.14 编程实践
-第十讲 操作符重载--编程实践提交入口
-11.1 提纲
-11.2 泛型编程概览
-11.3 异常处理机制（一）
-11.4 异常处理机制（二）
-11.5 运行期型式信息（一）
-11.6 运行期型式信息（二）
-11.7 模板与型式参数化
-11.8 题外话：术语翻译
-11.9 泛型编程实践（一）
-11.10 泛型编程实践（二）
-11.11 泛型编程实践（三）
-11.12 泛型编程实践（四）
-11.13 泛型编程实践（五）
-11.14 泛型编程实践（六）
-11.15 泛型编程实践（七）
-11.16 泛型编程实践（八）
-11.17 泛型编程实践（九）
-11.18 泛型编程实践（十）
-11.19 编程实践
-第十一讲 泛型编程--编程实践提交入口
-12.1 提纲
-12.2 程序执行环境（一）
-12.3 程序执行环境（二）
-12.4 程序执行环境（三）
-12.5 程序执行环境（四）
-12.6 输入输出（一）
-12.7 输入输出（二）
-12.8 文件系统
-12.9 设备
-12.10 库（一）
-12.11 库（二）
-12.12 makefile文件（一）
-12.13 makefile文件（二）
-12.14 makefile文件（三）
-12.15 编程实践
-第十二讲 Linux系统编程基础--编程实践提交入口
-13.01 提纲
-13.02 进程基本概念
-13.03 信号
-13.04 进程管理（一）
-13.05 进程管理（二）
-13.06 进程管理（三）
-13.07 进程间通信（一）
-13.08 进程间通信（二）
-13.09 进程间通信（三）
-13.10 进程间通信（四）
-13.11 进程池
-13.12 编程实践
-第十三讲 进程编程--编程实践提交入口
-14.1 提纲
-14.2 线程基本概念
-14.3 线程管理（一）
-14.4 线程管理（二）
-14.5 线程管理（三）
-14.6 线程管理（四）
-14.7 线程同步机制（一）
-14.8 线程同步机制（二）
-14.9 C++11线程库（一）
-14.10 C++11线程库（二）
-14.11 C++11线程库（三）
-14.12 C++11线程库（四）
-14.13 C++11线程库（五）
-14.14 编程实践
-第十四讲 线程编程--编程实践提交入口
-15.1 提纲
-15.2 Internet网络协议
-15.3 套接字（一）
-15.4 套接字（二）
-15.5 编程实践
-第十五讲 网络编程--编程实践提交入口
