1. 数据结构

数据结构与算法基础 - 图1

1.1 数据结构是什么？

数据结构是计算机存储、组织数据的一种方式。数据结构是指相互存在一种或多种特定关系的数据元素集合、进行选择的数据结构可以带来更高的程序运行或存储效率。数据结构与高效的检索算法和索引技术有关。

1.2 常见的数据结构有哪些？

  • 数组（Array）：数组是最基本的数据结构，它是将具有相同类型的若干变量有序的组织在一起。

数据结构与算法基础 - 图2

  • 栈 （Stack）：栈是一种特殊的线性表，它只能在一个固定的端点进行数据节点的插入和删除操作。栈按照先进后出的原则来存储数据。也就是说先插入的数据将被压入栈底，最后插入的数据在栈顶，读取数据时从栈顶逐个读取。

数据结构与算法基础 - 图3

  • 队列 （Queue）：队列也是一种线性表，和栈不同的是队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说进行插入操作的一端叫做队尾，进行删除操作的一端称为队头。

数据结构与算法基础 - 图4

  • 链表 （Linked List）：链表是物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针链接次序实现的。链表的么个节点都会包含两个部分一个是数据元素的数据域，一个是存储下一个节点的指针域。

image.png

  • 树 （Tree）：树是一种非线性结构，它是包括，2个结点的有穷集合K。在树结构中，有且仅有一个根结点，该节点没有前驱结点。在树结构中的其他节点都有且仅有一个额前驱节点，而且可以有两个后继节点，m≥0。

数据结构与算法基础 - 图6

  • 图 （Graph）：图也是一种非线性结构。在图结构中，数据结点一般被称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。

数据结构与算法基础 - 图7

  • 堆 （Heap）：堆是一种特殊的树形数据结构，一般讨论推都是二叉堆。堆的特点是根节点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。
  • 散列表 （Hash）：散列表源自于散列函数，其中心思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接去的所查记录。

数据结构与算法基础 - 图8

2. 算法

数据结构与算法基础 - 图9

2.1 算法的基本概念

算法是用于解决实际问题的一段程序代码，它有输入、输出并且具有确定性、有穷性和可行性

2.2 算法的五大特征

  • 有穷性：是可以被执行完成的，具有有限的执行次数。
  • 确定性：算法的执行范围是可以确定的。
  • 可行性：是可以解决实际问题的。
  • 有输入：可以有输入的条件。

  • 有输出：可以产生运行结果，没有结果的运行是没有任何意义的。

    2.3 算法的设计原则

  • 正确性：可以解决实际问题。

  • 可读性：算法程序代码能够快速被其他人看懂。
  • 健壮性：很少bug，程序代码运行稳定。

2.4 算法的两大指标

2.4.1 时间复杂度

基本概念

在算法中，时间复杂度用O表示，常见的时间复杂度有O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^n)，时间复杂度指的是运行一段程序所需要花费的时间。
计算时间复杂度往往是计算比较大的，而且是不确定的数，如果已经确定了，那就不用计算了，也就是我们说的常量。
O后面的括号中是一个函数，指明某个算法耗时与数据增长量之间的关系其中n代表输入数据的量
image.png
数据结构与算法基础 - 图11

数据结构与算法基础 - 图12

O(1)

O(1)表示是常数阶，所有能够被确定的执行次数都可以用O(1)表示，它是最低的空间复杂度，也是就是耗时与输入数据大小无关，无论输入数量增大多少倍，耗时都不变。哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到结果（在不考虑冲突的情况下）。

  1. public class HelloWorld{
  3.     public static void main(String[]args){
  5.         //时间复杂度 O(1)
  6.         System.out.println("Hello World!!!");
  8.         //时间复杂度 O(1)
  9.         for(int i = 0;i<=100;i++){
  10.            // ..... 省略逻辑
  11.         }
  13.     }
  15. }

O(logn)

O(logn)表示对数阶，当数据量增大n倍时，耗时增大logn倍（这里的log是以2为敌，比如当数据量增大256倍时，耗时只增加8倍，比线性还要低的时间复杂度）

  1. public class HelloWorld{
  3.     public static void main(){
  5.         //时间复杂度 O(logn)
  6.         int n = 100;
  7.         while(n > 1){
  8.             n = n * 2;
  9.         }
  10.     }
  12. }

O(n)

O(n)表示线性阶，表示数据量增大几倍，耗时量也得增大几倍

  1. public class HelloWorld{
  3.     public static void main(){
  5.         //时间复杂度 O(n)
  6.         int n = 未知大小;
  7.         for(int i = 0;i<=n;i++){
  8.            // ..... 省略逻辑
  9.         }
  11.     }
  13. }

O(nlogn)

O(nlogn)表示线性对数阶，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍，这个复杂度高于线性低于平方

  1. public class HelloWorld{
  3.     public static void main(){
  5.         //时间复杂度 O(n)
  6.         int n = 未知大小;
  7.         for(int i = 0;i<=n;i++){
  8.            // ..... 省略逻辑
  9.             while(n > 1){
  10.                 n = n * 2;
  11.             }
  12.         }
  14.     }
  16. }

O(n^2)

O(n^2)表示平方阶，当数据增大n倍时，耗时增大n^2倍

  1. public class HelloWorld{
  3.     public static void main(){
  5.         //冒泡排序 时间复杂度 O(n^2)
  6.         int[]arr = new arr[5]{{0,5,1,3,2}};
  8.         for(int i = 0;i < arr.length - 1;i++){
  9.             for(int j = i;j<arr.length - 1 - i;j++){
  10.                 int tmp = arr[j];
  11.                 arr[j] = arr[j+1];
  12.                 arr[j+1] = tmp;
  13.             }
  14.         }
  15.     }
  17. }

时间复杂度大小比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^n)

如何找出程序中的时间复杂度？

  1. 找有循环的地方
  2. 找有数据库查询的地方、RPC调用的地方

    2.4.2 空间复杂度

    基本概念

    空间复杂度，指的是运行一段代码所需要消耗的内存大小

    如何找出程序中的空间复杂度

    找程序代码中开了空间的地方，比如声明数组、链表的地方。