数据结构和算法之美

发表于 | 分类于

痛并快乐着。

复杂度分析

大O复杂度表示法(时间复杂度)

T(n) = O(f(n))
T(n)表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 例1
function cal1 (n) {
    let sum = 0;
    let i = 1;
    for(; i < n; ++i) {
        sum += i;
    }

    return sum
}

// 例2
function cal2 (n) {
    let sum = 0;
    let i = 1;
    let j = 1;
    for(; i < n; ++i) {
        j = 1;
        for(; i <= n; j++) {
            sum = sum + i * j
        }
    }

    return sum
}

假设每行代码的运行时间为x,例1中的第二三行代码，分别需要x个时间,第4、5行代码,各执行了n次,执行时间分别需要 n x。所以例1中代码执行时间需要(2n+2) x 。可以看出，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

所以例2中代码所需要的执行时间T(n) = 2n² + 2n + 3.
即: 所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势

时间复杂度分析

  • 只关注循环执行次数最多的一段代码。
    如例1中的代码，2、3行代码的执行时间都是常量级,与n的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。
  • 加法法则: 总复杂度等于量级最大的那段代码的复杂度
  • 乘法法则: 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
  • O(m+n)、O(m*n)
    如一个函数中有两个数据规模的量，在事先又无法评估谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。乘法一样。

最好、最坏情况时间复杂度

最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。
最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

比如要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值
(1 + 2 + 3 + … + n + n) / (n+1)

均摊时间复杂度

在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度
均摊复杂度在以下两个条件满足时使用

  1. 代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；
  2. 低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

空间复杂度

表示算法的存储空间与数据规模之间的增长关系。

数据结构类型

线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
数组，链表、队列、栈等都是线性表结构。

数组

数组,用一组连续的内存空间，来存储一组具有相同类型的数据。

  • 连续的内存空间和相同类型的数据
  • 支持随机访问
  • 低效的“插入”和“删除”
    如果某个数组中，需要在arr[x]的位置插入一个新的val，就需要将原来的x向后挪出一位，最坏的时间复杂度的情况为O(n)

链表

与数组相反，它并不需要一块一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。其中，我们把内存块称为链表的”结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。

单链表
1
--> data --> data -- > data --> null

单链表有两个结点比较特殊,头结点(第一个结点)和尾结点(最后一个结点指向null)

  • 插入删除非常便捷
  • 但随即访问没有数组高效，无法像数组一样通过下标获取，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。
循环链表

是一种特殊的单链表。
单链表的尾结点指向null(空地址),而循环链表的尾结点指针是指向链表的头结点.

双向链表。

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

  • 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

####链表与数组的对比

  • 数组大小固定，一经声明就要占用整块连续内存空间。链表本身没有大小的限制，天然地支持动态扩容。
指针

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

插入结点时一定要注意: 如果希望在a结点和b结点插入c结点，要先将c的next结点指向b，再将a的next结点指向c,这样才不会丢失指针，导致内存泄漏。同理，删除链表结点时，也一定要记得手动释放内存空间。

如何优雅的写出链表代码
  1. 理解指针或引用的含义
  2. 警惕指针丢失和内存泄漏（单链表）
  3. 利用“哨兵”简化实现难度
    链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。
  4. 重点留意边界条件处理
  5. 举例画图，辅助思考

栈

先进后出，后进先出。

  • 只允许在端插入和删除数据
  • 存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
  • 可以由数组实现

队列

先进先出

  • 最基本的操作有两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
  • 可以由数组实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

散列表

递归

指在运行的过程中调用自己。

构成递归需要满足的条件

  1. 一个问题的解可以分解为几个子问题的解。
  2. 子问题须与原始问题为同样的事,且更为简单。
  3. 存在递归终止条件。

如何编写递归

写出递推公式，找到终止条件。

如斐波那契数列。 1, 1, 2, 3, 5, 8, 13, 21, …

如何求 斐波那契数列第n项的值？

  1. 找出递推公式。 按数列不难发现，从第三项起，第三项的值，等于前两项值的和。
    及f(n) = f(n - 1) + f(n - 2)
  2. 终止条件
    当只有一个数时，值为1，所以 f(1) = 1。
    校验递归终止条件是否足够时，可以将n = 2,n = 3 带入地推公式里面实验一下。

当n = 2 时，f(2) = f(1) + f(0)。如果递归终止条件只有一个 f(1)=1，那 f(2) 就无法求解了。
所以除了f(1) = 1之外，还要有 f(0) = 1,用来表示0个数时的值，不过显然长度为0的数列是不符合正常逻辑的，所以，我们可以把f(2) = 2，当做一个 终止条件。
当n = 3时 …

把得到的递推公式和终止条件结合在一起:

1
2
3
f(1) = 1
f(2) = 2
f(n) = f(n -1) + f(n - 2)

有了公式，将其转换成代码就容易多啦。

1
2
3
4
5
6
// 时间复杂度 2^n  2的n次方
function fib(n) {
  if(n === 1) return 1
  if(n === 2) return 1
  return fib(n - 1) + fib(n - 2)
}

避免 OOM(内存溢出)

  1. 以通过在代码中限制递归调用的最大深度的方式来解决这个问题。及递归调用次数超过一定的深度(如1000以后)，我们就报错不再执行。

警惕重复计算

如果将上述代码的递归过程分解一下的话，不难发现有重复计算的问题。
如当 n为5时，f(5) = f(4) + f(3), 当n 为4时， f(4) = f(3) + f(2),这里的f(3)就重复计算了。
还是斐波那契数列求n项的值，为了避免重复计算，可以考虑将前两位数作为参数避免重复计算。

1
2
3
4
5
6
7
8
9
10
function fib(n) {
  function fun (n, fir, next) {
    if(n === 1) return fir
    if(n === 2) return next

    return fun(n-1, next, next + fir)
  }

  return fun(n, 1, 1)
}

排序

冒泡排序

核心原理

冒泡排序只会操作两个相邻的数据。每次冒泡排序都会对两个相邻的元素进行比较，看是否满足大小关系，如果不满足就让他俩互换，一次冒泡会至少让一个元素移动到他应该在的位置，重复n次就完成了n个数据的排序工作。

时间复杂度

最好时间复杂度 O(n)
最坏时间复杂度 O(n²)
平均时间复杂度 O(n²)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function bubbling(arr) {
  let len = arr.length; // 3

  if(len <=1 ) return

  for(let i = 0; i < len; i++) {
    let bool = false // 用于控制结束循环

    for(let j = 0; j < len - i - 1; j++) {
      if(arr[j] > arr[j + 1]) {
        let temp = arr[j] // 6
        let next = arr[j + 1]  // 3
        arr[j + 1] = temp // arr[1] = 6
        arr[j] = next // arr[0] = 3

        bool = true
      }
    }

    if(!bool) break

  }

  return arr
}

插入排序

核心原理

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，通常是数据的第一个元素。插入算法的核心思想就是取未排序区间中的数据，在已排序区间找到合适的位置将其插入，并保证已排序区间一直有序。重复这个过程，直到未排序区间数据为空，结束排序。

时间复杂度

最好时间复杂度 O(n)
最坏时间复杂度 O(n²)
平均时间复杂度 O(n²)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function insertSort(arr) {
  let len = arr.length

  if(len <= 1) return arr

  for(let i = 1; i < len; i++) {

    let j = i - 1
    let val = arr[i] // 3

    for(; j >= 0; j--) {
      if(arr[j] > val) {
        arr[j + 1] = arr[j] // 数据移动
      } else {
        break
      }
      
    }
    arr[j + 1] = val // 插入数据
  }

  return arr

}

选择排序

核心原理

选择排序的思路与插入排序的方法有些类似，也分为已排序区和未排序区。但是选择排序每次会在未排序区选择一个 最小值插入到已排序区末尾。

时间复杂度

最好时间复杂度 O(n)
最坏时间复杂度 O(n²)
平均时间复杂度 O(n²)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function selectSort(arr) {
  let  len = arr.length
  if(len <= 1) return arr

  for(let i = 0; i < len - 1; i++) {
    let minIndex = i;
    let minVal

    for(let j = i + 1; j < len; j++) {
      let currMinVal  =  arr[minIndex]
      let currEachVal = arr[j]
      if(currEachVal < currMinVal) {
        minIndex = j
      }
    }

    minVal = arr[minIndex]
    arr[minIndex] = arr[i]
    arr[i] = minVal
  }

  return arr

}

归并排序

排序原理

  1. 尽可能的将一组元素拆分成两个元素相等的子组(若无法相等向下取整保留前多后少)，并对每一个子组继续拆分，直到拆分后的每个子组中的元素个数为1为止。
  2. 将相邻的两个子组归并成一个有序的大组。
  3. 重复上述步骤直到归并成一个数组为止。

时间复杂度

最好时间复杂度 O(nlogn)
最坏时间复杂度 O(nlogn)
平均时间复杂度 O(nlogn)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function mergeSort(arr) {
  let len = arr.length
  if(len <= 1)  return arr

  let midIndex = Math.floor(len / 2) // 向下取整。如数据有5条，分割成 2, 3 

  let leftArr = arr.slice(0, midIndex)
  let rightArr = arr.slice(midIndex)

  return merge(mergeSort(leftArr),mergeSort(rightArr))

}

function merge(left, right) {
  let arr = []
  let leftIndex = 0
  let rightIndex = 0
  let leftLen = left.length
  let rightLen = right.length

  while(leftIndex < leftLen && rightIndex < rightLen) {
    let leftTempVal = left[leftIndex]
    let rightTempVal = right[rightIndex]

    if(leftTempVal <= rightTempVal) {
      arr.push(leftTempVal)
      leftIndex++
    } else {
      arr.push(rightTempVal)
      rightIndex++
    }
  }

  while(leftIndex < leftLen) {
    arr.push(left[leftIndex])
    leftIndex++
  }

  while(rightIndex < rightLen) {
    arr.push(right[rightIndex])
    rightIndex++
  }


  return arr

}

快速排序

核心思想

  1. 在数集中选择一个元素作为基准。
  2. 所有小于基准的元素，都移到基准的左边，大于基准的元素，都挪到右边。
  3. 对基准左右两边的数集，重复1,2 的步骤，直到所有的子集都只剩一个元素为止

时间复杂度

最好时间复杂度 O(nlogn)
最坏时间复杂度 O(nlogn)
平均时间复杂度 O(nlogn)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(arr) {
  let len = arr.length
  if(len <= 1) {return arr}

  let baseIndex = Math.floor(len / 2)
  let baseVal = arr.splice(baseIndex, 1)[0]

  let leftArr = []
  let rightArr = []

  for(let i  = 0; i < len; i++) {
    if(arr[i] < baseVal) {
      leftArr.push(arr[i])
    } else {
      rightArr.push(arr[i])
    }
  }

  return quickSort(leftArr).concat([baseVal], quickSort(rightArr))

}

桶排序

核心思想：

将要排序的数据，分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序后，再把桶里每个数据按照顺序依次取出，组成的序列就是有序的了。

计数排序

核心思想

当要排序的n个数据，所处的范围 并不大的时候，如最大值为k,则把数据划分成k个桶，这样桶里的数据都是相同的，相较于桶排序，省去了桶内排序的时间。

基数排序

####核心思想
需要分割出独立的“位”来比较，而且位之间有递进 关系，如果a数据的高位比b数据的大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

二分查找

核心思想

每次都取数据中的中间数来比较大小，从而不断地缩小查找范围，直至找到数据为止。

时间复杂度

O(logn)

使用限制

  1. 需要数据为数组类型；
  2. 需要数据为有序数据；
  3. 数据量太小、太大，均不适合使用二分查找。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 非递归
function basearch(arr, target) {
  let low = 0
  let high = arr.lenth - 1

  while(low <= high) {
    let mid  = Math.floor((low + high) / 2)

    if(arr[mid] === target) {
      return mid
    } else if(arr[mid] < target) {
      low = mid + 1
    }  else {
      high = mid - 1
    }
  }

  return false
}

// 递归
function basearch(arr, target) {
  return recursive(arr, 0, arr.length - 1, target)
}

function recursive(arr, low, high, target) {
  if(low > high) return false

  let mid = Math.floor((low + high) /2)

  if(arr[mid] ===  target)   {
    return mid
  } else if(arr[mid] < target) {
    return recursive(arr, mid + 1, high, target)
  } else {
    return recursive(arr, low, mid - 1, target)
  }

}

散列表 Hash Table

散列表用的是数组下标支持随机访问的特性，所以散列表其实是数组的一种扩展，由数组演化而来。

假如有50名学生参加学校运动会，为了方便记录成绩，会在胸前贴上编号，通过编号可以快速的查找到某个学生的成绩。

参赛学生的编号我们 叫做key,把参赛编号转化为数组下标的映射方法就叫作散列函数,而散列函数计算得到的值就叫作散列值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 找出两个数组中重复的项

let firstArr = [1, 2, 3, 4, 5, 6, 7]
let nextArr = [2, 4, 6, 8, 10, 9, 12]
function unque(firstArr, nextArr) {
  let map = {}, retArr = []
  firstArr.forEach(item => {
    map[item] = true
  })

  nextArr.forEach(item => {
    if(map[item]) {
      retArr.push(item)
    }
  })

  return retArr
}

树

释义

树结构

  • 节点：树上的每一个元素我们称之为节点；
  • 父子关系： 用来连接相邻节点之间的关系称之为父子关系；
  • 高度：节点到叶节点的最长路径(边数) 由下往上的度量。图中二图的高度为3(从零开始)
  • 深度：根节点到这个节点所经历的边的个数 由上往下度量，从0开始。
  • 层数：节点的深度 + 1。及层数的计算是由1开始。
  • 树的高度 = 根节点的高度

二叉树 Binary Tree

每个节点最多有两个叉，也就是最多两个子节点，分别为左节点和右节点。不过二叉树也并不要求每个节点都有左右节点，有的只有左节点，有的只有右节点。

二叉树

  • 满二叉树： 除了根节点外，每个节点都有左右两个子节点。
  • 完全二叉树： 最后一层的叶子节点都靠左排列，并且除了最后一层，其它层的节点数都打到了最大。

二叉树的存储

链式存储法
指针

时间复杂度 O(n)