前言

小白决定补一补计算机基础知识，欢迎路过的大佬各抒己见！

正文

数据结构与算法

数据结构是算法的基础，算法在特定的数据结构上才能发挥作用；数据存储结构会影响算法效率；

数据结构说明数据的组织方式，算法说明数据的操作方式。

数据结构和算法相辅相成，密不可分。

数据结构

社会中的万物如果要在计算机中表示和处理，需要用一种东西描述，叫做数据，不仅仅数字，文本、图像、视频、声音等都可以叫做数据。

描述数据又可以用数据元素、数据项、数据对象等。

举个例子：

表格中除表头外的每个单元格称为数据项，描述一个人的部分属性信息，是不可分割的最小单位。

表格中除表头外每一行称为数据元素，描述一个人的全部信息，若干个数据项构成一个数据元素，也称为记录；

整个表格称为数据对象，描述多个人的全部信息，相同特性的多个数据元素的集合，简称数据。

数据项> 数据元素> 数据对象 ，此处的>表示构成

数据结构，是指数据之间的组织方式，数据结构是数据之间是有特定关系而存在的一种体现。官方定义是：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构三要素

• 逻辑结构
• 存储结构
• 运算

数据结构的作用是为了在计算中方便表示数据和处理数据运算，分为逻辑结构、存储结构和运算。逻辑结构是从现实世界的具体问题出发抽象出的数学模型，用来描述数据之间的关系；存储结构是描述数据在计算中(内存中)的存储和关系体现，运算则是对数据的操作，通过运算来处理问题解决问题。

拿上面的例子来说，王立坤和王亦博是相邻的，王亦博和撒备宁是相邻的，这就是逻辑关系，如何在计算机中存储和表示王立坤、王亦博、撒备宁这三个数据元素及其相邻关系，这便是物理结构要做的事情。

抽象数据类型（ADT）

抽象数据类型(Abstract Data Type,ADT)是将数据对象、数据对象之间的关系、数据对象的操作封装在一起的一种结构，在Java编程语言中体现为一个类，不定义操作的具体实现，可以理解成逻辑结构的一种用计算机语言的表达，与编程所用的机器、所用的编程语言、所存储的结构均无关，。

它作为一种数据封装，只定义了功能，与具体的实现分离。是后面每一种数据结构在计算中描述使用的基础。

下面是抽象数据类型的标准格式：

ADT 抽象数据类型名称
Data 
   数据元素之间逻辑关系的定义
Operation 
   操作1 
      初始条件
      操作结果描述
   操作2
      ……
endADT

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

1. 算法的特性

● 输入和输出

有0个或多个输入，1个或多个输出

● 有穷性

在执行有限的步骤后可自动结束，每个步骤在可接受的时间内完成。

● 确定性

执行的步骤都是有确定含义，不会出现二义性。

● 可行性

每个步骤都可以通过有限次数运算实现。

2. 算法的设计要求

● 正确性

算法应能正确反应问题的需求，通过输入、输出和无歧义的加工处理，没有语法错误，对于合法的和非法的输入，能够得到问题的正确答案和相应的说明结果。

● 可读性

便于阅读、理解和交流。

● 健壮性

对于输入非法数据时，算法也能做出相应处理，而不是产生异常或其他莫名其妙的结果。

● 低存储空间

应尽量少的占用内存空间或外部硬盘存储空间。

● 高时间效率

算法运行应尽量消耗短的时间，或者说尽量缩短运算的执行次数。

3. 算法效率的衡量标准

● 时间复杂度

算法运行需要的时间称为时间复杂度，基本运算的执行次数做为时间复杂度的度量标准。时间复杂度一般是指最坏情况时间复杂度；时间复杂度函数中常数和其他次要项常常可以忽略，而更应该关注最高阶项的阶数。算法时间复杂度的计算方法参见博客：

时间复杂度的计算方法


常见的时间复杂度消耗的时间长度排序：O(1)<O(logN)<O(N)<O(NlogN)<O(N

^2)<O(N

3)<O(2

^N)<O(N!)<O(N

N)

● 空间复杂度

算法占用的空间大小称为空间复杂度。算法运行时辅助变量所占用的空间，是衡量空间复杂度的关键因素。

小结

加油吧，小白！。