绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
数据结构与算法概述
2020-05-19 15:12:28

初衷

学习数据结构与算法的知识,并没有一个完备的理由。如果是作为一名算法工程师,这无可厚非,但对于我们大部分的开发者而言,算法对工作的影响甚微,甚至可能不需要任何算法就可以完成全部的工作。那么,我们为什么要学习数据结构与算法?我总结有以下几点:

首先,算法是面试的常客。很多人会抱怨面试为何要问算法,工作中又用不到,调侃是面试造火箭,工作拧螺丝。但不可否认的是,算法可以排除一些滥竽充数的人。算法可以考察一个人的逻辑思维,应变力,也可以考察出现困难时的解决能力。所以,单从这个层面,我们应该学习算法。

其次,从个人发展而言,算法能够助我们突破瓶颈。随着工作年限的增加,我们做的工作也会从编程向优化倾斜,届时提高响应速度,解决系统瓶颈也会成为工作的主要内容之一。所以,如果要成为一名工程师,让自己在步入中年时不被淘汰,我们应该学习算法。

除此以外,还有一点原因十分重要。计算机技术飞速发展,各种新的语言、新的框架、新的思想层出不穷,铺天盖地的新技术没有人能够完全掌握。然而它们都可能不会长久,在不久后就会被更新的技术取代,也就意味着我们依托于此的积累都不复存在,(当然这部分知识也极为重要,不过我们应该分出一部分精力研究一些基础理论知识。但一些基础的理论不会被淹没,诸如计算机原理、操作系统原理、算法等,这些是计算机技术的基石。我们应该掌握不变的,以不变应万变,以免陷入吾生也有涯,而知也无涯。以有涯随无涯,殆已!的窘境。

既然选择了学习算法,首先要对一些基本概念有所认知。接下来的这些基本知识点,是我们每个人都必须深刻理解的,只有知道何为算法,为何需要算法,才能体会到学习算法的意义。

基础知识

计算机的存储结构

数据千变万化,但被加载到内存中的方式只有两种:顺序和链式。数据通常不是独立的,除数据本身外还有它和其他数据之间的关系,计算机能够表示数据和这种关系的方式只有这两种,它们的区别主要在于关系的表示上。

① 顺序存储结构

是指将数据存放在连续的存储单元中,通过相对位置来表示数据间关系,数组就是这一方式的典型实现。它在内存中结构示意图如下:

顺序存储示意图

② 链式存储结构

是指数据存放在任意的内存单元中,并为数据增加一个指针域,指向它的下一个(或上一个)元素的地址,以此来建立关系,我们使用的链表就是这一方式的典型实现。它在内存中结构示意图如下:

链式存储示意图

数据逻辑结构

数据之间同样都有联系,这种关系就是逻辑结构。通常有以下四类:

  1. 集合

指数据同属于一个集合,除此以外没有任何关系,这种关系很弱,不是研究的重点。示意图如下:

集合示意图
  1. 线性结构

是指数据之间是一对一的关系,例如数组和链表都是一对一的结构,示意图如下:

线性结构示意图
  1. 树形结构

是指数据之间存在一对多的关系,例如二叉树就是这种结构,示意图如下:

树形结构示意图
  1. 图形结构

是指数据之间存在多对多的关系,示意图如下:

图形结构示意图

算法定义

为了快速高效的把数据加载到计算机内存中,算法应运而生。它的定义如下:

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

算法的特性

  1. 输入输出

算法至少有零个或多个输入,至少有一个输出。一些特定的算法可以没有输入,但是算法必须有输出。

  1. 有穷性

算法必须在执行有限步数之后结束,且每一步都必须在有穷时间内完成。

  1. 确定性

算法的每一步都必须有确切的含义,且对于相同的输入,必须产生相同的输出结果。

  1. 可行性

算法必须是可以实现的,能够实际使用。理论上可以实现但现实上无法完成的算法不包括在内,这部分知识我们不进行研究。

算法的衡量标准

要设计一个可以使用的算法不难,但是算法也有优劣,衡量一个算法的好坏有以下几个标准:

  1. 正确性

算法的正确性,分为以下几个层面:

  • 实现算法的程序没有语法错误

  • 算法对合法的输入要产生满足要求的输出。

  • 算法对精心挑选的,苛刻的甚至刁难型的输入要能输出正确的结果。

  • 算法对于一切合法的输入都能产生正确的结果。

一般而言,满足前3点的算法都是合格的。

  1. 可读性

算法必须对人友好,难以理解的算法不实用,容易出错而且难以发现问题。

  1. 健壮性

也就是鲁棒性,算法必须能够处理各种错误的情况,并给出合理的解决方式。

  1. 效率高存储量低

算法的执行时间越短,占据存储的大小越小,算法就越好。

时间复杂度

影响算法运行时间的因素有很多,例如计算机的运算能力、编写算法使用的语言、算法的规模等。其中除了算法规模以外其他都与实际环境相关,所以主要衡量算法规模对时间的影响。算法的时间复杂度用T(n) = O(f(n))表示,也就是大O记法。其中n是数据的规模,意思是时间复杂度是规模的函数。

下面举几个例子说明这个函数的推导方法:

  1. 常数阶

int a = 10, b = 20;
System.out.println("sum of a and b is :" + (a+b));

像这种与规模无关的代码,其时间复杂度都是O(1)。因为无论a或者b多大,计算机都只需要执行以上两行代码即可。

  1. 线性阶

int sum = ;
for(int i=, len = 100; i<len; i++){
    sum += i;
}

当len的值不同时,for循环内部的代码需要执行的次数也不同,可以看到它需要执行len次,所以时间复杂度是O(n)

  1. 对数阶

int n = 100;
int count = 1;
while(count < n){
    count *= 2;
}

以上代码while循环部分也和n有关,但是它的执行次数并不是n次,可以看到count的值每次都乘2,也就是执行一定次数的乘2操作后,循环终止。相应的求解公式为2^x = n,可以得到x = log2n。通常省略下标,也就是时间复杂度为O(logn)

  1. 次方阶

int n = 100;
for(int i=; i<n; i++){
    for(int j=; j<n; j++){
        // 复杂度为O(1)的操作
    }
}

像这种双重for循环,其执行次数为n×n,所以时间复杂度为O(n^2)。再看下面的代码时间复杂度是多少呢?

int n = 100;
for(int i=; i<n; i++){
    for(int j=i; j<n; j++){
        // 复杂度为O(1)的操作
    }
}

这里仅是把j的起点从0换成了i。可以看到,当i=0时,j执行了n次;当i=1时,j执行了n-1次;…;当i=n-1时,j执行了1次。所以总的执行次数为:

n + (n-1) + (n-2) + … + 1 = n(n+1)/2 = n^2/2 + n/2。

从数学的角度来看,当n越大时,n/2对函数增长的影响越小,所以我们只需要关心n的高阶即可,以上的时间复杂度依然是O(n^2)

  1. 总结

通过以上几个实例,可以发现,时间复杂度并不是计算算法执行的时间,而是根据数据规模的一种估算,且仅考虑重要的因素:n的高阶。

在说时间复杂度时,通常有两个不同的概念:坏时间复杂度平均时间复杂度。比如要从一个数组中查询一个值,如果这个值就在位,那么只需要一次就找到了。如果这个数字在后一位,则必须对数组进行遍历,需要执行n次操作。这里前者就是好时间复杂度,为O(1),后者就是坏时间复杂度,为O(n)。平均时间复杂度则是指对所有可能情况需要的时间的均值,以上操作的平均时间复杂度为O(n/2)

很明显,平均时间复杂度更接近实际,但是实际中遇到的问题都远比上述例子复杂的多,它的平均时间复杂度很难计算,所以我们一般采用坏时间复杂度来衡量算法的效率

空间复杂度

是指算法运行时需要的存储空间的大小。这里的存储空间大小不包括代码本身、输入数据本身等所占据的空间,而是指为了实现算法所额外占用的空间,也就是和算法相关的那部分。比如为了实现算法,需要额外创建一个数组,来进行中转。算法的空间复杂度也是规模n的函数。

总结

有关数据结构和算法的基础知识就是这些,数据结构和算法的目的就是寻找高效的方式让计算机处理问题。相关的知识涉及到线性表、树、图等数据结构,还包括串、排序、查找、动态规划等内容。本系列文章会按照以下顺序对这些知识一一梳理:

  • 线性表,包括数组、链表、队列、栈等

  • 树,包括二叉树、二叉排序树、B树与B+树、赫夫曼树等

  • 串,包括KMP模式等

  • 查找,包括折半查找,索引,散列表等

  • 排序,包括冒泡、快速、选择、希尔、归并、堆等

  • 分治法、动态规划、贪心算法、回溯算法、分支限界法等

  • 图,包括小生成树、短路径、拓扑排序等

总结完基础知识后,还会对每个模块的经典题目进行练习。学会了数据结构,等于是掌握了九九乘法表,而进行算法题目的练习,就相当于使用九九乘法表解决实际问题。只有两者兼顾,才能真正理解数据结构,理解算法。


分享好友

分享这个小栈给你的朋友们,一起进步吧。

飞机酱的IT之旅
创建时间:2020-04-28 18:20:39
飞机酱是一个Android开发攻城狮,除了要攻陷Android外,还会进攻数据结构、算法、网络、计算机系统等方面的知识。关注我,一起学IT吧。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 大大纸飞机
    栈主

小栈成员

查看更多
  • ?
  • 小雨滴
  • 人工智能频道
  • 栈栈
戳我,来吐槽~