Skip to content

abcdabcd3899/Algorithms

BranchesTags

Repository files navigation

数据结构与算法

Github stars github language License Forks

1. 概述

包括但不限于以下内容：

2. 算法列表

细节题

Big Integer

经典算法应用

Bit Manipulation

Two pointers

prefix sum

sort

Intervals

Line Sweep

Data Structure

Binary Search

Trees, including Binary Search Tree, Binary Tree and N-ary Tree

Graph Algorithms

最短路径类型 算法 时间复杂度 算法类型
边权均为正，单源最短路径，稠密图 朴素dijkstra O(n^2) 贪心
边权均为正，单源最短路径，稀疏图 heap+dijkstra O(mlogn) 贪心
边权存在负值，单源最短路径，限制最短路径<=k bellman-ford O(nm) 离散数学、动态规划
边权存在负值，单源最短路径, 不限制 SPFA 平均情况下为O(m)，最坏O(nm) BFS优化bellman-ford
多源(起点)汇(终点)最短路径 floyd O(n^3) 动态规划
最小生成树类型 算法 时间复杂度 算法类型
稠密图 朴素prim O(n^2) 贪心
稀疏图 heap+prim O(mlogn) 贪心
稀疏图 kruskal O(mlogm) 贪心

注意：如果点数n和边数m在同一个数量级为稀疏图，如果m和n^2在一个数量级，则该图为稠密图。

math

Random/Shuffle/Reservior Sampling

Databases

Concurrency Algorithms

Shell Programming

3. 算法设计技术

Dynamic Programming

Greedy Algorithms

Brute Force Search

method extra space priorities Data Structure
DFS O(h) 无 stack
BFS O(2^h) shortest path(权重必须为1，否则不能找到最短路径)、topology sort queue

Recursive

Emumeration Search

4. 时空复杂度分析

4.1 理论

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

如上述代码，在上述代码中，只有for循环中的sum+=i被执行了 $n$ 次，其它代码的执行均与 $n$ 无关。本例中，我们将算法的时间复杂度表示为 $O(n)$，表示算法的执行时间与 $n$ 成线性比例。在算法分析中，用大 $O$ 表示时间复杂度，大 $O$ 不是算法的真正执行时间，而是表示代码的执行时间随数据规模增长的变化趋势，所有我们也称为渐进时间复杂度。常见的时间复杂度包括：

$O(1) &lt; O(lgn) &lt; O(n) &lt; O(nlogn) &lt; O(n^2) &lt; O(2^n) &lt; O(n!)$

在时空复杂度分析中，有下面三个法则：

  • 只关注循环执行次数最多的一段代码
  • 加法法则：总复杂度等于量级最大的那段代码的复杂度，该法则适用于多段平行代码段，总的时间复杂度为最大
  • 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

4.2 最好，最坏、平均、时间复杂度分析

4.1 节讲了基本的时间复杂度表示方法，本节将重点讲述最好、最坏、平均、均摊时间复杂度分析，这样便有了完整的时间复杂度分析方法。

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

上述代码的时间复杂度为 $O(n)$，代码性能较差，修改为下面部分：

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

如上代码，在最好情况下：数组的首元素的值与x相等，此时时间复杂度为 $O(1)$，在最坏情况下：遍历整个数组，但是仍然没有找到对应的元素，此时的时间复杂度为 $O(n)$。至于平均时间复杂度的分析稍微复杂一些，平均之间复杂度又称为期望时间复杂度或加权时间复杂度。在本例中，有 $n$ 个元素，每个元素都有 $1/n$ 的可能性被选中，并且被选中的元素有 $1/2$ 的可能性等于 $x$，因此：

$$1 * \frac{1}{2n} + 2* \frac{1}{2n} + ... + n * \frac{1}{2n} + n* \frac{1}{2}= \frac{3n+1}{4}$$

上述值就是每个位置可能出现等于x的情况的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该叫做加权平均时间复杂度或者期望时间复杂度。上述值用大 $O$ 表示为 $O(n)$。另外一种分析方法是，总共有 $n+1$ 种情况，找到该元素需要 $n$，1种情况下元素不在数组中，如下：

$$\frac{1+2+...+n+n}{n+1} = \frac{n(n+3)}{2(n+1)}$$

这种分析方法没有考虑每种情况出现的概率，不可取。

4.3 均摊时间复杂度分析

上述两节之后我们已经初步掌握了时间复杂度的分析方法，本节介绍均摊时间复杂度，均摊时间复杂度对应于算法中的摊还分析(或者叫平摊分析)。相比最好、最差、平均时间复杂度，均摊时间复杂度的使用场景更加特殊、更加有限。

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;

 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

这段代码实现了往数组中插入数据的功能。当数组满了之后，也就是代码中 count==array.length 时，通过 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将心得数据插入。当数组一开始有空闲位置时，则直接将数据插入数组。

最好情况下时间复杂度 $O(1)$，此时数组未满，并且由于count会自动执行加1操作，因此不用遍历找寻空位。

最坏情况下时间复杂度 $O(n)$，此时数组装满，首先需要遍历数组的全部元素执行累加操作，接着将累加后的和放入到数组的0位置上，然后count执行加1操作指向下一个位置，后续操作与最好情况下时间复杂度吻戏类似。

平均时间复杂度 $O(1)$：假设数组的长度为 $n$，根据插入的位置不同，可以将其分为 $n$ 中情况，每种情况的时间复杂度都为 $O(1)$，除此之外，还有一种当数组没有空闲位置时的情况，此时的时间复杂度为 $O(n)$，而且这 $n+1$ 中情况发生的概率一样，都是 $1/(n+1)$，所以根据加权平均的计算方法，平均时间复杂度为：

$$1 * \frac{1}{n+1} + 1* \frac{1}{n+1} ... + n * \frac{1}{n+1} = O(1)$$

到目前位置，最好情况下时间复杂度、最坏情况下时间复杂度、平均情况下时间复杂度的计算，理解起来都没有任何问题。但是这个例子的平均复杂度分析其实并不需要上述那样复杂，不需要引入概率论的知识。这是为什么呢？其实将本例的insert()和前面的find()进行对比，可以知道，find()函数在极端情况下复杂度才为 $O(1)$，但是insert在大部分情况下，时间复杂度都为 $O(1)$，只有当数组没有空闲位置时为 $O(n)$。其次对于insert()，插入时间复杂度为 $O(1)$ 和 $O(n)$ 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 $O(n)$ 插入只有，紧跟着 $n-1$ 个 $O(1)$ 的插入操作，循环往复。所以针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度，本文给其命名为均摊时间复杂度。那究竟如何使用摊还分析法来分析算法的均摊时间复杂度呢？

我们还是继续看在数组中插入数据的例子。每一次 $O(n)$ 的插入操作，都会跟着 $n-1$ 次 $O(1)$ 的插入操作，所以把时间耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 $O(1)$，这就是均摊分析的大致思路。均摊时间复杂度和弹摊还分析的应用场景比较复杂，所以我们并不会经常用到。为了方便理解和记忆，本文总结了一下它们的应用场景。如果你以后遇到了，知道是怎么回事就行了。

对一个数据结构进行的操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能够将较高时间复杂度的那次操作的耗时平摊到其它时间复杂度较低的操作上。而且，在能够应用平摊时间复杂度的分析场景中，一般均摊时间复杂度就等于最好情况下的时间复杂度。

尽管许多数据结构和算法书籍都花了很大的力气来区分平均时间复杂度和均摊时间复杂度，但是其实我认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多的精力去区分它们。我们应该花时间去掌握它的分析方法，摊还分析法。至于分析出来的结果叫平均还是均摊，并不重要。

4.4 总结

之所以引入最好时间复杂度、最坏时间复杂度、平均时间复杂度、均摊时间复杂度这些概念，是因为很多算法，在不同的输入情况下，算法的时间复杂度不一样。在引入这些概念以后，我们能够更加全面的表示算法的时间复杂度。

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10];
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}
/*答案：
最好时间复杂度O(1)，最坏时间复杂度O(n)，平均时间复杂度O(1)，均摊时间复杂度为O(1)
假设数组的长度为n，当数组未满时，每次往数组中添加元素的时间复杂度都为O(1)，当数组满时，需要O(n)的操作进行复制，并且这两个操作具有严格的时序关系，因此可以将复制的操作摊还给前面n-1次操作中，最终得到的时间复杂度仍然为O(1)
平均时间复杂度计算：
1 * 1/(n+1) + 1 * 1/(n+1)  ... + n * 1/(n+1)  = O(1)
*/

5. 参考文献

协议

更多信息参见协议文件。

署名-非商业性使用-禁止演绎。

About

Algorithms, Shell, SQL, Concurrency Solutions

Resources

Readme

License

GPL-3.0 license
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages