数据结构和算法入门

前言

为什么要学习算法和数据结构

  • 解决特定问题;
  • 深度优化程序性能的基础;
  • 学习一种思想:如何把现实问题转化为计算机语言表示。

业务开发要掌握到程度

  • 了解常见数据结构和算法,沟通没有障碍;
  • 活学活用:遇到问题时知道要用什么数据结构和算法去优化。

数据结构基础

什么是数据结构

数据结构是数据的组织、管理和存储格式,其使用目的是为了高效的访问和修改数据。
数据结构是算法的基石。如果把算法比喻成美丽灵动的舞者,那么数据结构就是舞者脚下广阔而坚实的舞台。

物理结构和逻辑结构的区别

物理结构就像人的血肉和骨骼,看得见,摸得着,实实在在,如数组、链表。
逻辑结构就像人的思想和精神,它们看不见、摸不着,如队列、栈、树、图。

线性存储结构和非线性存储结构的区别

线性:元素之间的关系是一对一的,如栈、队列。
非线性:每个元素可能连接0或多个元素,如树、图。

算法基础

什么是算法

  • 数学:算法是用于解决某一类问题的公式和思想;
  • 计算机:一系列程序指令,用于解决特定的运算和逻辑问题。

如何衡量算法好坏

  • 时间复杂度:运行时间长短,运行时间越短越好;
  • 空间复杂度:占用内存大小,占用内存越少越好。

时间复杂度

大 O 表示法(渐进时间复杂度):把程序的相对执行时间函数 T(n) 简化为一个数量级,这个数量级可以是 n、n^2 、logn 等。

推导时间复杂度的几个原则:

  • 如果运行时间是常数量级,则用常数1表示。
  • 只保留时间函数中的最高阶项。
  • 如果最高阶项存在,则省去最高项前面的系数。

时间复杂度对比:O(1) > O(logn) > O(n) > O(nlogn) > O(n^2)。
不同时间复杂度算法运行次数对比:

paste image

空间复杂度

  • 常量空间 O(1):存储空间大小固定,和输入规模没有直接的关系;
  • 线性空间 O(n):分配的空间是一个线性的集合,并且集合大小和输入规模n成正比;
  • 二维空间 O(n^2):分配的空间是一个二维数组集合,并且集合的长度和宽度都与输入规模n成正比;
  • 递归空间 O(logn):递归是一个比较特殊的场景。虽然递归代码中并没有显式的声明变量或集合,但是计算机- 在执行程序时,会专门分配一块内存空间,用来存储“方法调用栈”。执行递归操作所需要的内存空间和递归的深度成正比。

如何定义算法稳定性

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。

有哪些常见算法

首先要明确:特定算法解决特定问题。

  • 字符串:暴力匹配、BM、KMP、Trie等;
  • 查找:二分查找、遍历查找等;
  • 排序:冒泡排序、快排、计数排序、堆排序等;
  • 搜索:TFIDF、PageRank等;
  • 聚类分析:期望最大化、k-meanings、k-数位等;
  • 深度学习:深度信念网络、深度卷积神经网络、生成式对抗等;
  • 异常检测:k最近邻、局部异常因子等;
    ……

其中,字符串、查找、排序算法是最基础的算法。

坚持原创技术分享,您的支持将鼓励我继续创作!