前言

内功.jpeg

如果说,编程技巧为程序员的外功,那么数据结构与算法就是程序员的内功.
外功只要付出努力,勤奋点,大家都能练!
而内功的修炼,在需要勤奋的同时,还需要一点悟性! 这也是一个工程师的核心竞争力!
毕竟,现在编程几乎没有什么门槛了,无论之前什么行业,培训个几个月,几乎都能应付基本的业务开发工作.
所以,真正的工程师,一定要注重内功的修炼,建立其自己的技术护城河!

言归正传,通过此章,希望大家能收获以下知识

• 数据结构是什么
• 常用的数据结构
• 数据的逻辑结构和存储结构
• 算法及其评估标准
• 数据结构和算法的关系和区别

数据结构是什么

• 数据结构 (百度词条)

数据结构是计算机存储、组织数据的方式.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

从概念上很容易让人混乱, 又是存储,又是组织,又是关系的,到底数据结构是什么?

直白地讲,数据结构就是研究数据的存储方式.

因为组织数据,描述数据之间的关系,其实通通都是为了最后能够存储进电脑,并且需要的时候,能够完好无损的还原出来.

举两个简单的例子:

• 给你 1,2,3,4,5 这么一组有顺序的数字,请你存储进电脑.
  你肯定会用数组{1,2,3,4,5}来存储,因为数据能存储数值(1,2,3,4,5)又能存储它们之间的“顺序”关系.

• 假设给你张三,李四,王二,三个人, 张三是李四和王二的父亲,此时你如何存储呢?
  如果你还用数组{张三,李四,王二}来存储,显然数据存储是ok的,但是他们之间的关系却无法存储,此时,我们可以用“树”这种结构来存储.

  
  
  父子关系.png

总之,数据结构研究的就是数据的存储方式,最终目的就是为了完好的还原存放的数据及其数据之间的关系.

接下来,我们还需要理解几个计算机关于数据定义的概念(虽然我知道很枯燥)

• 数据(Data)

数据(Data)是能被计算机处理的符号或符号集合,含义广泛,可理解为“原材料”.如字符、图片、音视频等.

• 数据对象(Data Object)

是性质相同的数据元素的集合,是数据的子集(对应了OOP中的类),例如“黑人”,属于人类.

• 数据元素(Data Element)

组成数据的基本单位(对应了OOP中的对象),比如,在人类中,数据元素就是“人”,
而“人”可以有编号、姓名、性别、籍贯等数据项.

• 数据项(Data Item)

数据的不可分割的最小单位,一个数据元素可由若干个数据项组成.
比如,人这样的数据元素可以由眼,耳,手,鼻,口这些数据项组成

常用的数据结构

基本数据结构.png

数据的结构分类

数据的逻辑结构

数据的逻辑结构指的是数据中数据元素之间的逻辑关系.

数据元素之间存在不同的逻辑关系构成了以下4种结构类型:

• 集合结构

集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里.

• 线性结构

线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f-g·····被一根线穿连起来.

• 树形结构

树形的数据元素结构关系是一对多的,这就像张三,李四,王二,三个人, 张三是李四和王二的父亲

• 图结构

图的数据元素结构关系是多对多的.就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市.

由此,我们可以通过分析数据之间的逻辑关系来决定使用哪种存储结构,但具体使用顺序存储还是链式存储,还要通过数据的物理结构来决定.

数据的存储结构

数据的存储结构也称为物理结构,指的是数据的逻辑结构在计算机中的存储形式

直白点,就是数据在物理存储空间上选择集中存放(顺序存储结构)还是分散存放(链式存储结构).

• 顺序存储结构

是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的.

直白点:你把一堆鸡蛋放到了一个篮子里.

• 链式存储结构

是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系.

直白点:你把一堆鸡蛋分类放到了多个篮子里.

• 索引存储结构

索引存储，分别存放数据元素和元素间关系的存储方式。

直白点: 给每个鸡蛋唯一的编号,鸡蛋放在一个大篮子里,编号号牌放在一个小篮子里.

• 散列存储结构

散列存储，又称存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的技术

直白点: 给每个鸡蛋编号,按一定规律放到几个篮子里(假设有两个篮子,则按顺序放到两个篮子里.)

数据的逻辑结构和物理结构是密切相关的,在学习数据结构的过程中会发现,任何一个算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于所采用的存储结构.

算法及其评估标准

算法概念

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.

直白的讲,算法即解决问题的方法.

很多人误以为程序就是算法,其实不然:算法是解决某个问题的想法、思路;
而程序是在心中有算法的前提下编写出来的可以运行的代码.

例如,要解决依次输出一维数组中的数据元素的值的问题,首先想到的是使用循环结构(for 或者 while),在有这个算法的基础上,开始编写程序.

所以,算法相当于是程序的雏形.
当解决问题时,首先心中要有解决问题的算法,围绕算法编写出程序代码

算法的五大特性

1. 有穷性,是指算法在执行有限的步骤之后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成.
2. 确定性,是指算法执行的每一步骤在一定条件下只有一条执行路径,也就是相同输入只能有一个唯一的输出结果.
3. 可行性,是指算法每一步骤都必须可行,能够通过有限的执行次数完成.
4. 输入,是指算法具有零个或多个输入.
5. 输出,是指算法至少有一个或多个输出.

算法的评估标准

同一个问题,使用不同的算法,虽然得到的结果相同,但是耗费的时间和资源是不同的. 所以,便有必要对算法进行好坏的评估.

对于一个问题的算法来说,之所以称之为算法,首先它必须能够解决这个问题(称为准确性).其次,通过这个算法编写的程序要求在任何情况下不能崩溃(称为健壮性).

如果准确性和健壮性都满足,接下来,就要考虑最重要的一点:通过算法编写的程序,运行的效率怎么样.

运行效率体现在两方面:
算法的运行时间.(称为“时间复杂度”)
运行算法所需的内存空间大小.(称为“空间复杂度”)

好算法的标准就是:在符合算法本身的要求的基础上,使用算法编写的程序运行的时间短,运行过程中占用的内存空间少,就可以称这个算法是“好算法”.

时间复杂度

计算一个算法的时间复杂度,不可能把所有的算法都编写出实际的程序出来让计算机跑,这样会做很多无用功,效率太低.实际采用的方法是估算算法的时间复杂度.

在学习C语言的时候讲过,程序由三种结构构成:顺序结构、分支结构和循环结构.顺序结构和分支结构中的每段代码只运行一次；循环结构中的代码的运行时间要看循环的次数.

由于是估算算法的时间复杂度,相比而言,循环结构对算法的执行时间影响更大.所以,算法的时间复杂度,主要看算法中使用到的循环结构中代码循环的次数(称为“频度”).次数越少,算法的时间复杂度越低.

算法的时间复杂度的表示方式为大“O”记法:
T(n) = O(频度)

例如:
a) ++x; s=0;
b) for (int i=1; i<=n; i++) { ++x; s+=x; }
c) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }

上边这个例子中,a 代码的运行了 1 次,b 代码的运行了 n 次,c 代码运行了 n*n 次.
所以,对应的时间复杂度表示为:
a为T(n) = O(1)
b为T(n) = O(n)
c为T(n) = O(n^2)

如果a、b、c组成一段程序,那么算法的时间复杂度为O(n^{2+n+1).但这么表示是不对的,还需要对n}2+n+1进行简化.

简化的过程总结为3步:
去掉运行时间中的所有加法常数.(例如 n^2+n+1,直接变为 n^2+n)
只保留最高项.(n^2+n 变成 n^2)
如果最高项存在但是系数不是1,去掉系数.(n^2 系数为 1)

关于简化你可以这么理解:当n为无穷大的时候,在n^{2+n+1中,显然n}2才是最耗时间的.所以评估时,我们只看最耗时的即可.(长板效应)

所以,最终a、b和c合并而成的代码的时间复杂度为O(n^2).

常用的时间复杂度的排序(由小到大):
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义.

空间复杂度比较常用的有:O(1)、O(n)、O(n^2)
例如:
如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

再例如:

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

时间和空间的互换

算法的时间复杂度和空间复杂度是可以相互转化的.

现实生活中有很多空间换时间的例子,例如某些数学运算估计需要100年,这样的时间我们根本就等不起,但是存储空间我们可以制造,所以拿空间换时间是很划算的.

谷歌浏览器相比于其他的浏览器,运行速度要快.是因为它占用了更多的内存空间,以空间换取了时间.

算法中,例如判断某个年份是否为闰年时,
如果想以时间换取空间,算法思路就是:当给定一个年份时,判断该年份是否能被4或者400整除,如果可以,就是闰年.

如果想以空间换时间的话,判断闰年的思路就是:把所有的年份先判断出来,存储在数组中（年份和数组下标对应）,如果是闰年,数组值是1,否则是0；当需要判断某年是否为闰年时,直接看对应的数组值是1还是0,不用计算就可以马上知道.

数据结构和算法的关系

由于大量数据结构教程中都将数据结构的知识和算法掺杂起来讲,使很多初学者认为数据结构就是在讲算法,这样理解是不准确的.
数据结构和算法之间完全是两个相互独立的学科,两者既有联系又有区别.

我们从分析问题的角度去理清数据结构和算法之间的关系.通常,每个问题的解决都经过以下两个步骤:

1. 分析问题,从问题中提取出有价值的数据,将其存储；
2. 对存储的数据进行处理,最终得出问题的答案；

数据结构负责解决第一个问题,即数据的存储问题.通过前面的学习我们知道,针对数据不同的逻辑结构和物理结构,可以选出最优的数据存储结构来存储数据

而剩下的第二个问题,属于算法的职责范围.算法,从表面意思来理解,即解决问题的方法.我们知道,评价一个算法的好坏,取决于在解决相同问题的前提下,哪种算法的效率最高,而这里的效率指的就是处理数据、分析数据的能力.

因此我们得出这样的结论:

数据结构用于解决数据存储问题,而算法用于处理和分析数据,它们是完全不同的两类学科.

请关注我的订阅号

订阅号.png