常见的数据结构与算法

数据结构

数组、链表、队列、栈、散列表、二叉树、堆、跳表、图、Trie树

满二叉树
节点要么没有子节点，要有就一定得有两个子节点

完全二叉树
从根往下数，除了最下层外都有两个子节点，而最下层所有叶子结点都向左边靠拢填满（构造一颗完全二叉树就是从上到下、从左往右的放置节点）

堆（Heap）
我们常用的堆是基于完全二叉树结构实现的

  1. 根节点的值一定是最大（或最小）的（或之一）
  2. 父结点的值必然大于（或小于）等于它的任何一个子结点
  3. 同层节点之间没有必然的大小关系

跳表
跳表──没听过但很犀利的数据结构
https://lotabout.me/2018/skip-list/

Trie树
又称字典树、前缀树、单词查找树、键树等，是一种多叉树结构，基本性质

  1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符
  2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
  3. 每个节点的所有子节点包含的字符互不相同

算法思想

递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配

复杂度分析

  • 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述
  • 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述

时间复杂度

表示方法：大 O 符号表示法，即 T(n) = O(f(n))，并非衡量算法的真实执行时间，而是用来描述算法执行时间的增长变化趋势

常见的时间复杂度量级，复杂度依次递增，执行的效率越来越低：

  • 常数阶 O(1)
  • 对数阶 O(logN)
  • 线性阶 O(n)
  • 线性对数阶 O(nlogN)
  • 平方阶 O(n^2)
  • 立方阶 O(n^3)
  • k 次方阶 O(n^k)
  • 指数阶 O(2^n)
  • 阶乘阶 O(n!)

常数阶 O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O(1)；
即代码执行耗时不随着某个变量的增长而增长，即使代码成千上万行，都可以用 O(1) 来表示它的时间复杂度

对数阶 O(logN)

  1. int i = 1;
  2. while (i < n) {
  3.   i = i * 2;
  4. }

如上 while 循环里，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logN)

线性阶 O(n)
即算法的执行时间与某一变量的取值有关系

  1. for(i=1; i<=n; ++i){
  2.    j = i;
  3.    j++;
  4. }

有没有更简单直接的方式来得出一段代码的时间复杂度呢？ 有的，直接关注代码中循环执行次数最多的那段代码即可！

如上例，第2行代码和第3行代码显然就是循环执行次数最多的那段代码，那么𝑇(𝑛)=𝑂(2𝑛)，去掉系数，即可快速得出𝑇(𝑛)=𝑂(𝑛)

线性对数阶 O(nlogN)
将时间复杂度为 O(logN) 的代码循环 n 遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)

  1. for(m=1; m<n; m++){
  2.   i = 1;
  3.   while(i<n){
  4.     i = i * 2;
  5.   }
  6. }

平方阶 O(n^2)
即把时间复杂度为 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)

  1. for(x=1; i<=n; x++){
  2.   for(i=1; i<=n; i++){
  3.     j = i;
  4.     j++;
  5.   }
  6. }

同理，立方阶 O(n^3)、k 次方阶 O(n^k) 就相当于三层 n 循环、k 层 n 循环

阶乘阶 O(n!)

  1. int factorial(int n) { 
  2.   for (int i = 0; i < n; i++) { 
  3.     factorial(n - 1); 
  4.   } 
  5. }

循环执行次数最多的语句为 factorial(n - 1)，在当前 n 下，会调用n次factorial(n - 1)，而在每个 n−1 下，又会调用 n - 1次 factorial(n - 2)，以此类推，得执行次数为 n×(n−1)×(n−2)×…×1，即 n!

最好时间复杂度、最坏时间复杂度、平均时间复杂度

空间复杂度

空间复杂度也不是用来计算程序实际占用的空间的，是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义；空间复杂度比较常用的有：O(1)、O(n)、O(n²)

空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

  1. int i = 1;
  2. int j = 2;
  3. ++i;
  4. j++;
  5. int m = i + j;

空间复杂度 O(n)

  1. int[] m = new int[n]
  2. for(i=1; i<=n; ++i)
  3. {
  4.    j = i;
  5.    j++;
  6. }

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

空间复杂度O (n²)
递归函数反复调用自身 n 次，由于只有当函数调用到最后一层时才会结束一层调用，而之前的调用由于没有结束从而被一直压入栈中，导致空间无法得以重复利用，所以空间复杂度为𝑂(𝑛2)

注意：如果传递的是指针或引用，由于它们都会指向原本的内存空间，因此不需要分配新的存储单元

参考链接

算法的时间与空间复杂度（一看就懂） 不复杂的时间复杂度 https://blog.csdn.net/zjulyx1993?type=blog 算法