基本数据单位

数据：所有能输入到计算机中去的描述客观事物的符号

数据对象：相同特性数据元素的集合，是数据的一个子集

数据元素：数据的基本单位，也称结点（node）或记录（record）

数据项：有独立含义的数据最小单位，也称域(field)

如下图

基本数据单位

假设有一座学校，这个学校就是数据。那么学校中的老师，学生，教室等就是数据对象。单个老师、学生和教室就是数据元素。单个老师和学生的信息，如姓名身高体重等就是一个个数据项。

数据结构

数据结构可以从两个视角划分，分别是逻辑结构和物理结构。

逻辑结构

逻辑结构是按数据元素间的逻辑关系来划分的，分成集合结构、线性结构、树形结构和图形结构。

集合结构和线性结构

集合结构：一种松散的逻辑结构，元素之间除同属该集合这一联系外没有其他的关系。如哈希表。

线性结构：一对一，集合中必存在唯一的一个“第一个元素”和“最后一个元素”，除最后一个元素之外，其他数据元素均有唯一的"后继"，除第一元素之外，其它数据元素均有唯一的"前驱"。如线性表，栈，队列，字符串等。

树形结构

树形结构：一对多，在树形结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点。叶子结点没有后续结点，其余每个结点的后续节点数可以是一个也可以是多个。如二叉树。

图形结构

图形结构：多对多，在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。

其中除了线性结构外的三种又统称为非线性结构。

物理结构

物理结构是按数据的物理存储方式来划分的，分成顺序结构和链式结构。

顺序结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。直白点就是用一段连续的地址存放数据元素，数据间的逻辑关系和物理关系相同，便于查询数据。

链式结构：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).它不要求逻辑上相邻的元素在物理位置上也相邻，便于插入删除。

算法

算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列列,并且每个指令表示⼀一个或多个操作。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法的特性包括：有穷性，确定性，可行性，输入和输出。而评价一个算法的优劣，也不能仅仅依靠空间复杂度和时间复杂度，还需要考虑到其正确性、可读性和健壮性。

大O符号

算法的时间/空间复杂度常用大O符号来表示，大O符号计算时，对于确定的结果都取常数阶1，对于不确定的则只保留最高阶，不保留低阶项和首项系数，其考虑的是一个算法在最坏情况下的复杂度。常见的复杂度如下图

常见复杂度

时间复杂度

相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为T(n)，定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数T(n) 的自然特性加以分类，举例来说，有着T(n) =O(n) 的算法被称作“线性时间算法”；而T(n) =O(M^n) 和M= O(T(n)) ，其中M≥n> 1 的算法被称作“指数时间算法”。

在我看来其实就是计算一个算法需要执行的次数。如

常数阶

其中不管输入n为多少，执行次数都是唯一确定的3次，根据大O表示法则为常数阶O(1)。

线性阶

这段算法则根据输入n的不同，执行次数也不同，需要执行n次，则其复杂度为O(n)。

对数阶

执行次数为log2 n，则其复杂度为O(log n)，log2，log3，log10都不用考虑，仅记作log。

平方阶

立方阶

平方阶和立方阶同理，不过只保留最高阶，最高阶的首项系数和其他阶都忽略。

空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数。我们常说的空间复杂度一般指算法中需要的辅助空间。比如交换数组中元素的位置，如果使用中间变量来实现，那么就只需要一个中间变量，则其空间复杂度就是常数阶O(1)；如果用另一个数组来存储的话，则会根据数组元素个数n的不同，使用n个不同的空间，所以其空间复杂度就是O(n)。

参考资料：

https://www.jianshu.com/p/32eca07444d5、https://www.cnblogs.com/surenjiesu/p/11514312.html、百度百科。