算法设计与分析基础--基本概念

有两种思想,就像摆放在天鹅绒上的宝石那样熠熠生辉,一个是微积分,另一个就是算法.微积分以及在微积分基础上建立起来的数学分析体系造就了现在科学,而算法则造就了现代世界. ———大卫.柏林斯基

什么是算法

算法: 是一系列解决问题的明确指令,也就是说,对于符合一定规范的输入,能够在有限时间内获得要求的输出.

算法的特点:

  1. 算法的每一个步骤都必须没有歧义,不能有半点含糊.
  2. 必须认真确定算法所处理的输入的值域.
  3. 同一算法可以用不同的形式来描述.
  4. 同一问题,可能存在不同的算法.
  5. 针对同一问题的算法可能基于完全不同的解题思路,而且解题速度也会有显著不同.

算法问题求解基础

算法是问题的程序化解决方案.


算法设计分析过程的经典步骤

理解问题

从实践角度看,在设计算法之前,我们首要要对给定问题有完全的理解.应该仔细阅读问题描述,有疑惑就提出来.试着手工处理一些小规模的例子,考虑一下特殊的情况,有必要时继续提出疑问.
算法的输入,确定了该算法所解问题的一个实例.严格确定算法需要处理的实例范围很重要(边界值).

注意: 正确的算法不应该能处理大多数常见的情况,而且应该能正确的处理所以的合法的输入.因此,第一步很重要,否则不得不冒返工的危险.

了解计算设备的性能

我们使用的大多数算法仍运行在类冯.诺依曼系统上.这个体系结构的根本在于随即存取机(RAM:Random Access Machine).它的最主要的假设是:指令逐条运行,每次执行一步操作.相应的,设计在这种机器上运行的算法成为顺序算法(Sequential Algorithm).一些更新式的计算机打破了RAM模型的核心假设,它们可以在同一时间执行多条指令,即并行计算.能够利用这种计算机能力的算法称为并行算法(Parallel Algorithm).

在精确解法和近似解法之间做出选择

精确解法对应的算法为精确算法(Exact Algorithm).近似解法对应的是近似算法(Approximation Algorithm).有些无法求出精确值,比如在求平方根,解线性方程和求微积分.其次,由于某些问题固有的复杂性,用已知的精确算法来解决该问题可能会很慢.所以,一个近似算法可以作为更负责的精确算法的一部分.

算法的设计技术

确定适当的数据结构

算法的描述

算法的正确性证明

算法的分析

为算法写代码

重要的问题类型

排序

查找

字符串处理

图问题

组合问题

几何问题

数值问题

基本数据结构

线性数据结构

集合与字典

小结

文章目录
  1. 1. 什么是算法
  2. 2. 算法问题求解基础
    1. 2.1. 理解问题
    2. 2.2. 了解计算设备的性能
    3. 2.3. 在精确解法和近似解法之间做出选择
    4. 2.4. 算法的设计技术
    5. 2.5. 确定适当的数据结构
    6. 2.6. 算法的描述
    7. 2.7. 算法的正确性证明
    8. 2.8. 算法的分析
    9. 2.9. 为算法写代码
  3. 3. 重要的问题类型
    1. 3.1. 排序
    2. 3.2. 查找
    3. 3.3. 字符串处理
    4. 3.4. 图问题
    5. 3.5. 组合问题
    6. 3.6. 几何问题
    7. 3.7. 数值问题
  4. 4. 基本数据结构
    1. 4.1. 线性数据结构
    2. 4.2.
    3. 4.3.
    4. 4.4. 集合与字典
  5. 5. 小结