数据结构与算法基础——第01周-算法与算法分析1(1.4)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 数据结构与算法的研究内容

二 算法的定义

对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作
简而言之，算法就是解决问题的方法

1
2
3
Step1:...
Step2:...
Step3:...

三 算法的描述

3.1 自然语言：英文、中文

1
2
3
4
5
6
算法：求一元二次方程的根
1. 输入方程的系数a、b、c
2. 判断a是否等于零。如果等于零，则提示不是一元二次方程。不等于零，则执行第3步
3. 计算d=b^2-4ac
4. 判断d。如果d等于零，计算并输出两个相等实根。如果d小于零，输出没有实根。如果d大于零，输出两个不等实根
5. 结束

3.2 流程图：传统流程图、NS流程图

传统流程图

NS流程图

3.3 伪代码：类语言：类C语言

伪代码（Pseudocode）是一种非正式的，类似于英语结构的，用于描述模块结构图的语言

伪代码：是用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法

1
2
3
4
5
6
7
Begin（算法开始）
输入 A，B，C
IF A>B 则 A→Max
否则 B→Max
IF C>Max 则 C→Max
Print Max
End （算法结束）

3.4 程序代码：C语言程序、Java语言程序

四 算法与程序

4.1 算法

  • 算法是解决问题的一种方法或一个过程
  • 考虑如何将输入转换成输出，一个问题可以由多种算法

4.2 程序

  • 程序是用某种程序设计语言对算法的具体实现
  • 程序=数据结构+算法
  • 数据结构通过算法实现操作
  • 算法根据数据结构设计程序

4.3 算法特性

一个算法必须具备以下五个重要特性

  • 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成
  • 确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出
  • 可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现
  • 输入：一个算法有零个或多个输入
  • 输出：一个算法有一个或多个输出

4.4 算法设计的要求

正确性(Correctness)

正确性：算法满足问题要求，能正确解决问题，算法转换为程序后要注意：

  1. 程序中不含语法错误
  2. 程序对于几组输入数据能够得出满足要求的结果
  3. 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果
  4. 程序对于一切合法的输入数据都能得到满足要求的结果

通常以第三层意义上的正确性作为衡量一个算法是否合格的标准

可读性(Readability)

  1. 算法主要是为了人的阅读和交流，其次才是为了计算机执行，因此算法应该易于人的理解
  2. 另一方面，晦涩难度的算法易于隐藏较多错误而难易调试

健壮性(Robustness)

  1. 指当输入非法数据时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结构
  2. 处理出错的方法，不应是终端程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理

高效性(Efficiency)

  1. 要求花费尽量少的时间和尽量低的存储需求