当前课程知识点：基于Linux的C++ > 第四讲 算法 > 4.7 容错与计算复杂度 > LinuxCPP0407
接下来这个知识点呢
我们就称它为容错
容错是什么东西呢
容错就是允许错误的发生
写了一个程序
你要说这个程序一点错误都没有
那种情况几乎是不可能的
不仅仅说你的程序代码中
有可能隐藏着一些
隐含的bug你没有调出来
就是用户在运行程序的时候
都有可能发生错误
正常的情况下面
我们应该允许错误的发生
并且在错误发生的时候能够知道
按照什么样的方式
对它进行正确地处理
在程序的运行过程中
可能会遇到几种类型的错误
第一种就是很少见的特殊情况
或者普通错误 这种错误忽略了
对这个程序影响其实也不算特别大
有没有这种可能呢 也有这种可能
比如说输出一段错误的信息
这个信息输出多了 没有意义
结果导致整个程序输出不好看
对于正规程序来讲其实也算bug
但是它不重要 这样的错误可以不管
但是还有一种就是用户输入的错误
就是我们前面讲日期那个例子
年份、月份我都有了 你给我一个日期
12月的话日期只有1到31天
你给我一个0那可不成
你给我一个250还是不成
这是非常重要一个地方
用户输入数据是错误的
同学们在写程序的时候要特别记得
如果你这个程序写出来一个bug
那肯定是你的问题
用户输入一个错误的数据
他一定会怪你的
你这是什么程序连这个错误都处理不了
所以这是程序员的责任
不管谁的责任 最终都是程序员的责任
写程序的时候就需要特别去注意这一条
用户输入的错误
重要性数据
一定要对它进行数据有效性检查
在用户输入错误的数据之后要通知用户
告诉他这个信息错了
给他一个机会让他重新输入
直到他给了你一个正确值为止
正常情况下 你的逻辑应该是这个样子
反正用户没办法 跟程序比耐心
第三种就是致命错误
程序出现了一个巨大的错误
不能再做下去了 再做下去的话
这个错误所造成的后果会传播
结果错误会越放越大
后果就非常非常严重了
这个时候我们就要通知用户
这个错误的性质 然后停止执行
这个就叫致命错误
一定要按照这个方式进行处理
所以说典型容错手段
用户输入错误的话
我们就应该用数据有效性检查
而对于致命错误
我们要保证在任何时候
程序流程都能够提前终止
代码中有这两部分东西就叫容错了
看看刚才那个例子
如果我真是要输入这样一个数据
那我们应该怎么去解决它
想想我们原来例子
当用户输入数据是无效的
那我就提醒你 你输入错误的数据了
那么合规的数据应该是什么东西
最好也给他提示
然后重新去获取用户的数据
当这个数据重新获取完这个数据
还是不对的时候
你进一步提醒他 再拿到新的数据
一定要更正成正确的数据
这就叫数据的有效性检查
所以正常情况下面
需要使用一个while循环
来去做这件事情的
一定要按照这个模式进行工作
你的程序代码才是健壮的
我们来看看素性判定函数第六版
这个第六版
和刚才那个实现就不太一样
不涉及到数据有效性检查
它涉及到的是程序流程的提前终止
就是原来判定这个素性的时候
有一个最基本一个要求
就是这个数大于2
定义的参数是unsigned int
是一个非负整数
它可不是全是大于2的数
它还有0 它还有1 它还有2
那0、1、2这三个数怎么办
我们要考虑这个问题
首先我们可以把2这个问题给解决掉
if(n==2) 那我就直接return true
它是个素数 再往下去
然后再看它是不是偶数
if(n%2==0) 我们return false
这样就把2这个问题给解决了
那么如果是0或者1怎么办
如果n<=1
那我们就输出一个提示信息
叫素性测试失败
调用一个函数叫exit来退出
就是安全出口
这个函数在哪里定义的呢
是在“stdlib.h”里定义的
C++里面使用“cstdlib”
这个函数它要带一个参数
这个参数是一个整数值
它将这个参数传给exit
然后exit将把这个值返回给Linux操作系统
Linux操作系统接受这个值以后
可以通过下一个程序
或者通过一个技术手段
来得到这个程序的返回值
基本的约定俗成的习惯就是
当你这个程序正确执行的时候
应该返回0
当它发生1号错误的时候返回1
当它发生2号错误的时候返回2
当它发生3号错误的时候返回3
至于什么是1号错误
2号错误和3号错误
程序编完了 你应该写一个帮助手册
用户在使用你这个程序的时候
一查帮助手册 看到这个返回值 一对照
就知道你这个程序因为什么原因出错了
能够有的放矢做一些后续的处理
这一讲还有最后一小节
给同学们引入一个
算法复杂度基本概念
我们说衡量一个算法的好坏
就是它的效率和性能
怎么去表示它呢
你说这个算法比那个算法快
你比如像欧几里得算法
肯定要比最大公约数穷举法要快
那么它到底快了多少 怎么去描述它呢
所有这些东西
都需要定性或定量的方案描述它
正常情况下
算法的执行时间是问题规模的函数
我们称它为算法的复杂度
严格讲起来它是算法的时间复杂度
还有一种就是这个算法
使用到多少内存空间
那叫空间复杂度
以前这两种都很重要
现在内存容量很大
大部分时候都用不完
所以这种情况下面我们关注的
往往是时间复杂度
算法的效率和性能
如果能够定量来描述当然会很好
但是算法比较的时候
定性的表达其实就足够了
这种表达式 在计算机理论里面
称为大O表达式
它有两个基本原则
这两个基本原则就是
第一 忽略所有对这个算法复杂度
影响较小的项
第二 和问题规模无关的常数全忽略
比如3n*n+100n
那么100n先砍掉不要了
然后3不要了
结果它大O表达式就是O(n*n)
这就是算法复杂度一个近似的描述
有一些标准算法复杂度的类型
比如说常数级我们称它为O(1)
就表示这个算法的执行时间
和问题规模没有关系
不管问题规模有多大
它都是常数时间内都能够给你解决
还有log(n) 那是对数级的
还有一种呢 平方根级的
就像素性判定 平方根级别的
还有一个呢 O(n) 线性级的
比它更差的 就是n乘上log(n)级别的
然后更差n平方级别的
还有n的立方级别的 这都不算差
有些问题到目前为止
我们只能找到r的n次方 这就很慢了
还有n!的 你想象一下它是多慢
那么对于同学们来讲 看到一个算法
怎么估计它的算法复杂度呢
有一个基本技巧
就是数循环嵌套了多少次
一般情况来讲 一次循环
它就是O(n)级别的
嵌套了两重循环它就O(n*n)级别的
注意这地方有一点小细节
就是如果真是一个嵌套的两层循环
那么第一层循环是i小于等于根号n
第二个循环j小于等于根号n
那么它也是O(n)的级别的
不是n的平方级别的
这个地方要特别注意
-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 编程实践
-第十五讲 网络编程--编程实践提交入口
