数据结构与算法-基础篇

前言

最近开始学习数据结构与算法的知识,看了《数据结构与算法图解》这本书,了解了数据结构与算法的一些知识,解决了自己以前的一些困惑,这里做一个总结,加深记忆。

数据结构与算法可以潜移默化的提高程序员的内在素质和代码水平。

一、基础概念

算法:

算法就是解决某个问题的流程,类似于数学题的解法,而程序代码就是算法的语言实现。

数据涉及的操作:

在计算机世界里,算法是指某项操作的过程,包括读取、查找、插入和删除。
读取:查看数据结构中某一位置上的数据;
查找:从数据结构中找出某个数据值的所在;
插入:给数据结构增加一个数据值;
删除:从数据结构中移走一个数据值;

大O计法:

表示算法性能和时间复杂度的一种通用方式。(大O计法一般都是指最坏情况)

常数时间

O(1):一步
O(N):对于N个元素的数据结构,需花N步。

对数时间

O(logN):当数据量翻倍时候,步数增加1。

2、时间复杂度:

操作的速度,并不按照时间计算,而是按步数计算。数据结构与算法操作的速度,被称为时间复杂度;

二、数组:

数组是计算机科学最基本的数据结构之一。数组是计算机内存中连续的一组格子,内存中的每个格子都有各自的地址(编号),每个格子的内存地址比前一个大1。

image.png

1、读取:
数组读取只需要一步。(数组本身会记有数组第一个元素的内存地址,所以可以直接获取某一索引的数据)
2、查找:
对于数组来说,查找就是检查他是否包含某个值。
对于N格的数组,数组查找需要N步。
3、插入:
数组插入新元素的速度,取决于插入的位置。在数组末尾插入,只需要一步,但在其他位置插入,需要移动别的元素,
一个含有N个元素的数组,其插入数据最坏情况会花费N+1步。
4、删除:
数组删除就是消掉某个索引上的数据。
对于N格的数组,删除操作最多需要N步。

三、集合

集合,是一种不允许元素重复的数组结构。(其他与数组基本相同)

1、读取:
集合读取只需要一步。
2、查找:
对于N格的集合,集合查找需要N步。
3、插入:
集合插入与数组不同,计算机首先要确定插入的值不存在与其中,所以每次插入需要先进行一次查找。
对于N格的集合,集合插入的最坏情况为2N+1步,N步查找,N+1步插入。
4、删除:
对于N格的集合,删除操作最多需要N步。

四、散列表

散列表由一对对的数据组成,一对数据里,一个叫做键,一个叫做值。java中的map对象。
散列表的原理是通过散列函数对键进行计算,得到一个散列值,这个散列值代表散列表的值存储的内存格子。所以散列表读取数据只需O(1),它总是先计算出键的散列值,然后根据散列值跳到对应格子。

五、栈和队列

1、栈

栈存储数据的方式跟数组一样,不过它有以下三条约束:

  • 只能在末尾插入元素
  • 只能读取末尾的数据
  • 只能移除末尾的数据

栈适用于处理临时数据情景,特别是当数据的处理顺序要与接收顺序相反时。比如撤销操作等;

2、队列

队列与栈相反:

  • 只能为末尾插入数据
  • 只能读取开头数据(跟栈相反)
  • 只能移除开头数据(跟栈相反)
    队列适用于处理有序处理事情的长期,比如排队等;

六、递归

函数调用自身,就叫做递归。

对于大多数循环能够解决的问题,用递归也可以解决,但不代表应该用。递归适宜与解决有多层嵌套的情况,比如多级菜单树的生成。

评论

暂无评论