限制含义
- 界限
- 令人无法忍受事情（比如软件工程中的BUG）
1. 硬件限制
1.1 算数运算的限制
计算机硬件对整数和实数的表示限制：
整数
- 计算机硬件决定了它能表示的数字的限制；
- 超出数据会溢出；
- 溢出问题可以通过程序克服（一系列小数通过链表表示大数）；
实数
- 精度：计算机内存单元最多可以表示的有效位数
- 实数：符号位、指数符号位、指数位、数值位
- 表示误差或舍入误差：算数运算结果的精度大于计算机的精度造成的算术误差
- 下溢：计算出来的绝对值太小，计算机无法表示
- 溢出：计算值结果太大，计算机无法表示
- 化零误差
1.2 通信限制
策略
- 检错码：盘点数据传输过程中是否产生了错误
- 误差校验码：识别错误的同时，还能判断正确值是什么。
奇偶校验
- 用于检测存储在读或者写一个字节，或者发送或接收一个字节过程中发生的错误
- 奇校验：要求一个字节+一个校验位后，其中有奇数个1
- 偶校验
校验数位
- 校验每个数的和（34376=>每位之和为23）
- 检测的错误越重要，检测算法越复杂
误差校验码
当出现故障时候，可以基于另一个副本得到正确的值； 误差校验码主要用在硬盘驱动器，做数据冗余，防止硬盘故障数据丢失；
2. 软件限制
2.1 软件复杂度
以前一个程序员解决一个问题，现在一个问题由一组程序员解决；
引入软件工程的分支；
2.2 提高软件质量方法
软件工程
- 计算机问题求解过程：指定需求、编写规约、开发算法、实现算法、维护程序
- 软件需求：产品功能描述
- 软件规约：产品功能特性说明，比如功能、输入、处理、输出
- 软件生命周期
- 需求分析
- 制定规约
- 软件设计（高层、低层）
- 软件实现
- 维护
- 软件走查和审计：在测试开始之前发现错误
- 走查：小组用样本测试程序，模拟验证程序员实现需求的方法
- 审查：由非程序开发人员，逐行读出审查的需求、设计、代码，让小组成员以发现更多的错误
- 软件错误量衡量：指定行数的错误率
- 标准软件：每1k行25个bug
- 好的软件：每1k行2个bug
- space shuttle软件：每1w行少于1个bug
臭名昭著的软件错误
- AT&T，交换系统停9小时
- Therac-25，射线过量
- 91年海湾战争，飞毛腿导弹误伤，精度偏差
- 99年火星飞船烧毁，度量转换问题
- 62年金星探测器销毁，句号写成了逗号
3. 计算机问题
3.1 算法比较
大O分析
- 大O符号：以函数中随着问题规模增长最快的项来表示计算时间（复杂度）的符号
- 宠物店比喻，买大象和金鱼，忽略金鱼的价格
- O(N): N表示问题的大小，在数据结构中，表现为结构中元素的个数
- 把一个列表所有元素写入一个文件（
打开，然后N*(读+写)），算法复杂度O(N) - 家庭洗衣量，函数复杂度为O(N)：
f(N) = c*N，c为平均每人衣服洗完耗费时间，N为家庭人数
常见的数量级
- O(1): 有界时间/固定时间，工作量为常数，比如：给具有N个元素的数据中第i元素赋值
- O(log2N): 对数时间，每次问题数据减少一半，比如：二分检索
- O(N)：线性时间，比如：无数列表N中，找一个数；输出N个元素的所有元素；
- O(Nlog2N): NlogN时间，要经过N次对数算法，比如快速排序、堆排序、归并排序（快排在特定输入数据下为O(N^2)）
- O(N^2)：二次时间，通常要用N次线性算法，大多数简单排序比如冒泡、选择排序时间复杂度都是O(N^2)
- O(2^N): 指数时间，非常耗时的算法，比如国王和稻谷的故事
- O(N!): 阶乘时间，货郎担图论算法
算法分类
- P类算法
- NP类算法
- 指数算法/阶乘算法
- 不可解决算法
P类、NP类问题
- 多项式时间算法：复杂度能用问题大小N的多项式表示的算法；
- P类：有所有多项式时间算法构成的类；
- P类问题：用一个处理器能在多项式时间内解决的问题
- NP类问题：用足够多个处理器能在多项式时间内解决的问题
- NP类完全问题：NP类问题子集
其他
- 图灵机
- 停机问题：确定对于指定的输入一个程序最终是否停止的问题是不可能解决的。
4. 小结
- 软件、硬件，以及问题自身都对问题的解有限制
- 软件复杂度一定会导致错误，好的构建方式是及早关注软件质量，做好工程规划
- 从非常容易解决的到根本不能解决的问题种类很多
- 使用基于大O的分析，可以根据问题规模大小N，来决定增长速率来对比算法优劣
- P类问题与NP类问题，以及图灵停机问题