【数据结构基础笔记】第一章绪论之算法及算法分析

小咪咪 2021-06-11 15:12 472阅读 0赞

**目录**

一、简要

1、涵盖内容

2、学习要求

3、参考书目

二、重要笔记

1、算法

2、算法效率度量

--------------------

# 一、简要 #

第一章一共四小节，只有第四节单独作为一个博客发表，不仅仅是这一节在我心中地位比较重要，这一节在考研，期末考试和以后的码农生涯都会有重要作用。我不能说我这一节总结的有多好，但我还是希望能拿出来与大家分享。

## 1、涵盖内容 ##

1、算法的定义、算法的基本特性以及算法分析的基本概念。

2、算法的设计要求，效率度量方式以及存储空间需要。

## 2、学习要求 ##

1、掌握算法的五个重要特性及特点；

2、掌握评价算法的标准，会计算时间复杂度和空间复杂度。

## 3、参考书目 ##

《数据结构（C语言版）》严蔚敏、吴伟民 编著  清华大学出版社

# 二、重要笔记 #

## 1、算法 ##

### 1.定义 ###

算法（algorithm）是**对特定问题求解步骤的一种描述**，他是指令的有限序列，其中一条指令表示一个或多个操作。

### 2.五个重要特性 ###

（1）**有穷性**：一个算法必须总是（对任何合法的输入值）**在执行有穷步之后结束**，且**每一步都可能在有穷时间内完成**。

（2）**确定性**：算法中每一条指令**必须有确切的含义**，**读者理解时不会产生二义性**，在任何条件下，**算法只有唯一的一条执行路径**。对于**相同的输入只能得到相同的输出**。

（3）**可行性**：一个算法是能行的，**算法中描述的操作都是可以通过已实现的基本运算执行有限次来实现**。

（4）**输入**：一个算法有**零个或多个输入**。取自某个特定的对象的集合。

（5）**输出**：一个算法有**一个或多个输出**。同输入有某种特定关系的量。

### 3.算法目标 ###

（1）**正确性**：算法应当满足具体问题的需求，并**能正确的解决求解问题**。

（2）**可读性**：算法主要是为了人的阅读和交流，其次才是机器执行，可读性**有助于人对算法的理解**，晦涩难懂的算法难以调试和修改。

（3）**健壮性**：当**输入非法数据时，算法也能适当做出反应或进行处理**，而不是产生莫名其妙的输出结果。

（4）**效率与低存储量需求**：效率指的是算法执行的时间，存储量需求是指算法执行过程中所需要的最大的存储空间，这两者都**与问题的规模有关**。

## 2、算法效率度量 ##

### 1.度量方法 ###

（1）**事后统计的方法**

缺陷：依据算法编制的程序；依赖计算机硬件，软件等环境因素，容易掩盖算法本身的优劣。

（2）**事前分析估算的方法**

取决于以下因素：算法策略；问题规模；书写程序的语言（实现语言级别越高，执行效率越低）；编译所产生的机器代码质量；机器执行指令速度。

### 2.时间复杂度 ###

一个语句的频度是指**该语句在算法中被执行的次数**，算法中所有的语句的频度之和记作T(n)，它是该算法问题规模n的函数，记作

![70][]

它表示随着问题规模n的增大，算法执行时间的增长率和  f(n)  的增长率相同。称之为算法的**渐近时间复杂度**，简称**时间复杂度**。

（1）**常用时间复杂度**

![70 1][]

**注：越往下，算法的时间复杂度越高，编写算法时尽量避免使用指数阶。**

（2）**时间复杂度分类**

**最坏时间复杂度**：最坏情况下的时间复杂度。

**平均时间复杂度**：所有输入实例等概率出现的期望运行时间。

**最好时间复杂度**：最好情况下的算法时间复杂度。

**注：一般总是考虑最坏时间复杂度，保证算法的运行时间不会比它更长。**

### 3.空间复杂度 ###

**算法的所消耗的存储空间，即算法的空间复杂度**。记为：

![70 2][]

**算法原地工作**：算法所需要的辅助空间是常量，即O(1)。

[70]: /images/20210516/b147d0605dd64323a25370faa0c22edb.png
[70 1]: /images/20210516/eb46d5c12d6741788414b8fc7268343c.png
[70 2]: /images/20210516/3528f204e0e348c598884661cface163.png

发表评论取消回复

表情：

评论列表（有 0 条评论，472人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构第一章绪论

1. 问题求解与程序设计 2. 数据结构的基本概念 3. 算法的基本概念 4. 算法分析 5. 扩展与提高 > 刚开始学数据结构加上没接触过语言，感觉有点难 ![

左手的ㄟ右手/ 2023年10月08日 08:57/ 0 赞/ 18 阅读

相关数据结构与算法学习笔记（第一章绪论）

这章知识点概念比较多，我就画了一张逻辑图来表示了，这样看起来清晰明了。（第一次用XMind，逻辑图第二章以后的内容还没写，持续更新中。。。。。。） ![在这里插入图片描述

悠悠/ 2023年07月20日 08:25/ 0 赞/ 80 阅读

相关数据结构习题——第一章绪论

整理自己学习过程中接触的习题，不断更新中。答案在每个部分后面。第一部分：第一章绪论一．选择题 1．数据结构被形式地定义为（K，R），其中K是①的有

﹏ヽ暗。殇╰゛Y/ 2022年11月01日 04:29/ 0 赞/ 297 阅读

相关数据结构和算法绪论

逻辑结构：是指数据对象中数据元素之间的相互关系。使我们重点要关注和讨论的问题。四大逻辑结构： ①集合结构 ②线性结构 ③树形结构 ④图形结构存储结构有两种：

古城微笑少年丶/ 2022年08月03日 12:46/ 0 赞/ 129 阅读

相关数据结构学习笔记第一章绪论

目录数据结构的起源数据结构的基本概念算法和算法分析 stl与数据结构内容 1.数据结构的起源：算法+数据结构=程序数据结构=逻辑结构+储存

谁借莪１个温暖的怀抱￠/ 2022年05月28日 00:53/ 0 赞/ 233 阅读

相关数据结构和算法分析：第一章引论

1.2 数学知识和复习 1.2.1 指数 ![在这里插入图片描述][70] 1.2.2 对数 ![在这里插入图片描述][70 1] ![在这里插入图片描

今天药忘吃喽~/ 2022年05月11日 15:16/ 0 赞/ 211 阅读

相关数据结构和算法绪论

数据结构：是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。 • 程序设计 = 数据结构 + 算法数据结构就是关系，没错，就是数据

古城微笑少年丶/ 2022年03月22日 04:46/ 0 赞/ 259 阅读

相关数据结构和算法分析：第二章算法分析

算法是为求解一个问题所要遵循的，被清楚指定的简单指令的集合。 2.1 数学基础相对增长率大O标记法 ![在这里插入图片描述][20190228150856882

た入场券/ 2022年03月15日 01:54/ 0 赞/ 185 阅读

相关【数据结构基础笔记】第一章绪论之算法及算法分析

目录一、简要 1、涵盖内容 2、学习要求 3、参考书目二、重要笔记 1、算法 2、算法效率度量 -------------------- 一、简要

小咪咪/ 2021年06月11日 15:12/ 0 赞/ 473 阅读

相关【数据结构基础笔记】第一章绪论之基本概念

目录一、简要 1、涵盖内容 2、学习要求 3、参考书目二、重要笔记 1、基本概念 2、数据结构 -------------------- 一、简要

野性酷女/ 2021年06月11日 15:12/ 0 赞/ 503 阅读