数据结构和算法基础知识总结

# 1、复杂度

# 1.1 时间复杂度

在进行算法分析时，语句总是随着执行次数 T(n) 是关于问题规模 n 的函数。进而分析 T(n)的数量随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间量度，记做 T(n)=O(f(n))。它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度，是算法的执行时间与数据规模之间的增长关系。其中 f(n) 是问题规模 n 的某个函数。

# 1. 时间复杂度分析

只关注循环执行次数最多的一段代码。
加法法则：总复杂度等于量级最大的那段代码的复杂度。

///cal()函数的时间复杂度是n^2
function cal( n) {
   let ret = 0; 
   let i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
   for(let j=0;j<n;j++){
       for(let p=0;p<n;p++){
           console.log(j);
       }
   }
 }

1
2
3
4
5
6
7
8
9
10
11
12
13

乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

//cal()函数的复杂度是n*2
function cal( n) {
   let ret = 0; 
   let i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
function f( n) {
  let sum = 0;
  let i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 2、时间复杂度量级分类

多项式量级

常数阶(O(1))
对数阶(O(logn)) 因为对数之间是可以互相转换的。log3n=log10n/log103= log32 * log2n=(log102/log103)*(log10n/log102)，所以就有O(log3n)=O(C*log2n),C=log32是一个常量。在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n)))=O(f(n)),所以在对数阶时间复杂度的表示方法里,会忽略对数的"底"，统一表示为O(logn)。
```
//时间复杂度为O(log2n)
const n=10;
let i=1; 
while (i <= n) { 
    i = i * 2; 
}
////时间复杂度为O(log32n)
const n=10;
let i=1; 
while (i <= n) { 
    i = i * 3; 
}
```
1
2
3
4
5
6
7
8
9
10
11
12
线性阶(O(n))

//m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。
function cal( m,  n) {
  let sum_1 = 0;
  let i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  let sum_2 = 0;
  let j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

线性对数阶(O(logn))
平方阶(O(n^2))、立方阶(O(n^3))...k次方阶(O(n^k))

非多项式量级

指数阶(O(2^n))
阶乘阶(O(n!))

# 3、时间复杂度情况分类

// n表示数组array的长度
//最好情况复杂度是O(1)
//最坏情况复杂度是O(n)
function find(array,  n,  x) { 
    let i = 0; 
    let pos = -1; 
    for (; i < n; ++i) { 
        if (array[i] == x) { 
            pos = i; 
            break; 
        } 
    } 
    return pos;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

最好情况时间复杂度(极端情况的复杂度)
最坏情况时间复杂度(极端情况的复杂度)
平均情况时间复杂度(加权平均时间复杂度)

//上面代码中x一共有n+1(在数组的0~n-1位置和不在数组中)中情况，每种情况下查找需要遍历的元素个数依次是(1,2,3....n,n),要么在数组中要么不在数组中的概率都是1/2。根据概率乘法。有以下公式
//=>1/2n表示x为1的概率
1/2n+2/n+.....+n/2n+n*1/2=(3n+1)/4

1
2
3

均摊时间复杂度

# 1.2 空间复杂度

通过计算算法所需的存储空间实现。S(n)=O(f(n))，其中 n为问题的规模，f(n)为语句关于 n 所占存储空间的函数。空间复杂度的全称是**渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。**一般会在函数中以数组的形式存在。一维数组的话空间复杂度就是数组的长度 （n）。二维数组的空间复杂度为 n^2。常见的空间复杂度就是O(1)、O(n)、O(n^2)

# 2、数据结构

# 2.1、线性表

锳锳零个或多个数据元素的有限序列。

# 1、线性表的顺序存储结构

用一段地址连续的存储单元依次存储线性表的数据元素。

优点

无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速的存取表中任意位置的元素。

缺点

插入和删除需要移动大量元素。
当线性表长度变化较大时难以确定存储空间的容量。
造成存储空间的碎片。

# 2、线性表的链式存储结构

对数据元素来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储额信息称为指针或链这两部分信息组成结点。多个节点链接成一个链表，称为线性表的链式存储结构。

# 2.1、单链表

链表中的每个节点只包含一个指针域，称为单链表。链表中的第一个节点的存储位置称为头指针。在单链表的第一个结点前附设一个结点，称为头结点。头结点的指针域存储指向第一个结点的指针。线性链表的最后一个节点指针为空（通常用NULL表示）

头指针

指链表中指向第一个节点的指针。
头指针具有标识作用，所以常以头指针冠以链表的名字。
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点

头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义。
有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作和其他结点的操作就统一了。
头结点不一定是链表必须元素。

单链表和顺序存储结构的优缺点

1、存储分配方式

顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

2、时间性能

查找
- 顺序存储结构 O(1)
- 单链表 O(n)
插入和删除
- 顺序存储结构 O(n)
- 单链表 O(1)

3、空间性能

顺序存储结构需要预分配存储空间，空间分大了，浪费，分小了容易发生上溢。
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。数据元素可以存在内存未被占用的任意位置。

# 2.2、静态链表

用数组描述的链表。数组的元素由两个数据域组成，data和cur。data用来存放数据元素，cur相当于单链表中的 next 指针。

优点

在插入和删除操作时，只需要移动游标，不需要移动元素，从而改进在顺序存储结构中的插入和删除操作要移动大量元素的缺点。

缺点

没有解决连续存储分配带来的表长难以确定的问题。
失去了顺序存储结构随机存取的特性。

# 2.3、循环链表

将单向链表中终端结点的指针端由空指针改为指向头结点，就使单链表形成一个环，这种首位相连的单链表称为循环链表。

# 2.4、双向链表

在单链表的每个节点中，再设置一个指向其前驱结点的指针。

# 2、栈和队列

# 2.1 栈

栈是限定仅在表尾进行插入和删除操作的线性表。允许删除和插入的一端称为栈顶，另一端称为栈底。栈又被称为后进先出的线性表(Last In First Out),简称LIFO操作。

# 2.2 队列

队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。是一种先进先出(First In First Out)的线性表。

← 数据结构之树的基础知识算法之查找 →