数据结构与算法-经典算法总结

• 这取决于给定更高阶输入时算法的效率。
  
• 值的可能限制/约束。
  
• 计算机的体系结构和要使用的存储设备的种类。
  
• 另一个重要方面是算法的正确性，这意味着如果对于每个实例，它都产生正确的输出，则该算法是正确的。不正确的算法可能根本不会在某些输入实例上停止，或者给出不正确的输出。
  

• 互联网是智能高效算法的结果，借助这些算法，Internet 上的各个站点都能够管理和操纵如此大量的数据。找到数据传输的良好路线，并使用搜索引擎查找存在特定信息的页面。
  
• 人类基因组计划，它朝着识别人类 DNA 中的 100000 个基因的目标取得了长足的进步，确定了构成人类 DNA 的 30 亿个化学碱基对的序列，并将这些大量信息存储在数据库中，并开发用于数据分析的工具。这些步骤中的每一个都需要复杂而高效的算法。
  
• 日常电子商务活动，很大程度上依赖于我们的个人信息，例如信用卡/借记卡号码、密码、银行对账单、OTP 等。使用的核心技术包括基于数值算法和数论的公钥加密货币和数字签名。
  
• 线性规划的方法也是一种被广泛使用的技术，在几乎不需要以最有利的方式分配资源的制造和其他商业企业中。
  
• 最短路径算法也有广泛的用途， Internet 上的路由节点可能需要找到通过网络的最短路径，以便快速路由消息。
  
• 即使是在应用程序级别不需要算法内容的应用程序也严重依赖算法，因为应用程序依赖于硬件、GUI、网络或面向对象，所有这些都广泛使用算法。
  

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else   
        return n*fact(n-1);   
}

• 递归中有两种情况，即递归情况和基本情况。
  
• 基本情况用于在情况成立时终止递归函数。
  
• 每个递归调用都会在堆栈内存中创建该方法的新副本。
  
• 无限递归可能会导致堆栈内存不足。
  
• 递归算法示例：合并排序、快速排序、河内塔、斐波那契数列、阶乘问题等。
  

• Kruskal 的最小生成树 (MST)：在 Kruskal 的算法中，我们通过一个接一个地选择边来创建一个 MST。贪婪选择是在迄今为止构建的 MST 中选择不会导致循环的最小权重边缘。
  
• Prim 的最小生成树：在 Prim 的算法中，我们通过一个接一个地选择边缘来创建一个 MST。我们维护两组：一组已包含在 MST 中的顶点和一组尚未包含的顶点。贪婪选择是选择连接两组的最小权重边。
  
• Dijkstra 的最短路径：Dijkstra 的算法与 Prim 的算法非常相似。最短路径树是边接边建立的。我们维护两组：一组已包含在树中的顶点和一组尚未包含的顶点。贪婪选择是选择连接两个集合的边，并且在从源到包含尚未包含的顶点的集合的最小权重路径上。
  
• 霍夫曼编码：霍夫曼编码是一种无损压缩技术。它将可变长度位代码分配给不同的字符。贪婪选择是将最少位长度的代码分配给最常见的字符。
  

示例 2：考虑以下 6 个按完成时间排序的活动。
     start[] = {1, 3, 0, 5, 8, 5};
     finish[] = {2, 4, 6, 7, 9, 9};
一个人最多可以进行四项活动。求可以执行的最大活动集是 {0, 1, 3, 4} [这些是 start[] 和
finish[] 中的索引]

• 根据完成时间对活动进行排序
  
• 从排序后的数组中选择第一个活动并打印。
  
• 对排序数组中的剩余活动执行以下操作。 a) 如果此活动的开始时间大于或等于先前选择的活动的结束时间，则选择此活动并打印。
  

)
        {
                cout <<" " << j;
                i = j;
        }
        }
}

// driver program to test above function
int main()
{
        int s[] = {1, 3, 0, 5, 8, 5};
        int f[] = {2, 4, 6, 7, 9, 9};
        int n = sizeof(s)/sizeof(s[0]);
        printMaxActivities(s, f, n);
        return 0;
}
//this code contributed by shivanisinghss2110
时间复杂度：如果输入活动可能无法排序，则需要 O(n log n) 时间。当输入活动总是被排序时，它需要 O(n) 时间。
4.2 数组中的贪心算法

给定一个数组 a，我们必须找到数组中存在的元素子集的最小乘积。最小乘积也可以是单个元素。
输入： a[] = { -1, -1, -2, 4, 3 }
输出： -24
解释：最小乘积为 ( -2 * -1 * -1 * 4 * 3 ) = -24

算法思路：

• 如果有偶数个负数且没有零，则结果是除最大值负数之外的所有负数的乘积。
  
• 如果有奇数个负数并且没有零，则结果只是所有的乘积。
  
• 如果有零和正数，没有负数，则结果为 0。例外情况是当没有负数且所有其他元素为正数时，我们的结果应该是第一个最小正数。
  

算法实现：
// CPP program to find maximum product of
// a subset.
#include <bits/stdc++.h>
using namespace std;

int minProductSubset(int a[], int n)
{
        if (n == 1)
                return a[0];
        // Find count of negative numbers, count of zeros,
        // maximum valued negative number, minimum valued
        // positive number and product of non-zero numbers
        int max_neg = INT_MIN, min_pos = INT_MAX, count_neg = 0,
                count_zero = 0, prod = 1;
        for (int i = 0; i < n; i++) {
                // If number is 0, we don't multiply it with
                // product.
                if (a == 0) {
                        count_zero++;
                        continue;
                }
                // Count negatives and keep track of maximum valued
                // negative.
                if (a < 0) {
                        count_neg++;
                        max_neg = max(max_neg, a);
                }
                // Track minimum positive number of array
                if (a > 0)
                        min_pos = min(min_pos, a);
                prod = prod * a;
        }
        // If there are all zeros or no negative number present
        if (count_zero == n || (count_neg == 0 && count_zero > 0))
                return 0;
        // If there are all positive
        if (count_neg == 0)
                return min_pos;

        // If there are even number of negative numbers and
        // count_neg not 0
        if (!(count_neg & 1) && count_neg != 0)
                // Otherwise result is product of all non-zeros
                // divided by maximum valued negative.
                prod = prod / max_neg;
        return prod;
}

int main()
{
        int a[] = { -1, -1, -2, 4, 3 };
        int n = sizeof(a) / sizeof(a[0]);
        cout << minProductSubset(a, n);
        return 0;
}

// This code is contributed by Sania Kumari Gupta
4.3 图中的贪心算法

最小生成树 (MST)或最小权重生成树是权重小于或等于所有其他生成树的权重的生成树。生成树是一个子图，它是一棵树，将所有顶点连接在一起。一个图可以有许多不同的生成树。
Kruskal 算法查找 MST 的步骤

• 按权重的非递减顺序对所有边进行排序。
  
• 选择最小的边。检查它是否与到目前为止形成的生成树形成一个循环。如果没有形成循环，则包括该边。否则，丢弃它。
  
• 重复步骤#2，直到生成树中有 (V-1) 条边。
  

Prim算法查找 MST 的步骤

• 创建一个集合mstSet来跟踪已包含在 MST 中的顶点。
  
• 为输入图中的所有顶点分配一个键值。将所有键值初始化为 INFINITE。将第一个顶点的键值指定为 0，以便首先拾取它。
  
• 虽然 mstSet 不包括所有顶点 a)选择一个在mstSet中不存在且具有最小键值 的顶点u 。b)将u包含到 mstSet。 ……c)更新u的所有相邻顶点的key值
  

算法实现参照：咖喱：《大话数据结构之七：图》
4.4 操作系统中的贪心算法

• 内存管理中的 First Fit 算法
  
• 内存管理中的最佳拟合算法
  
• 内存管理中的最差拟合算法
  
• 操作系统 | 内存管理中的 Next Fit 算法程序
  
• 最短作业优先调度
  
• 最短作业优先 (SJF) 调度程序 | 第 2 组（抢先）
  
• 调度作业，使每台服务器获得相同的负载
  
• 一次允许两个作业的作业调度
  
• 在有限的时间内安排优先任务并最大限度地减少损失
  
• 最优页面替换算法程序
  
• 页面替换算法程序 | 设置 1 (LRU)
  
• 页面替换算法程序 | 设置 2（先进先出）
  

5.动态规划

动态规划（DP）是一种算法范式，它通过将给定的复杂问题分解为子问题并存储子问题的结果以避免再次计算相同的结果来解决给定的复杂问题。关键点：重复调用相同输入的递归解决方案
以下是问题的两个主要属性，表明可以使用动态规划解决给定问题。

重叠子问题
像分而治之，动态规划结合子问题的解决方案。动态规划主要用于反复需要相同子问题的解决方案时。在动态规划中，子问题的计算解决方案存储在一个表中，因此不必重新计算这些解决方案。因此，当没有常见（重叠）子问题时，动态编程没有用处，因为如果不再需要解决方案，存储解决方案毫无意义。
最优子结构
如果给定问题的最优解可以通过使用其子问题的最优解来获得，则给定问题具有最优子结构性质。

如何解决动态规划问题？

第 1 步：如何将问题归类为动态规划问题？
通常，所有需要最大化或最小化特定数量的问题或计数问题，即计算特定条件下的排列或特定概率问题，都可以通过使用动态规划来解决。所有的动态规划问题都满足重叠子问题的性质，大多数经典动态问题也满足最优子结构的性质。有一次，我们在给定问题中观察这些属性，确保它可以使用 DP 解决。
第 2 步：确定状态
DP 问题都是关于状态及其转换的。这是最基本的步骤，必须非常小心地完成，因为状态转换取决于您选择的状态定义。状态状态可以定义为一组参数，这些参数可以唯一地标识给定问题中的某个位置或站立。这组参数应该尽可能小，以减少状态空间。
第 3 步：建立状态之间的关系
这部分是解决 DP 问题中最难的部分，需要大量的直觉、观察和实践。让我们通过考虑一个示例问题来理解它
第 4 步：为状态添加记忆或表格
这是动态规划解决方案中最简单的部分。我们只需要存储状态答案，以便下次需要该状态时，我们可以直接从记忆中使用

常见动态规划问题数字动态规划：

有许多类型的问题要求计算两个整数之间的整数“x ”的数量，例如“a”和“b”，使得 x 满足可以与其数字相关的特定属性。因此，如果我们说G(x)表示 1 到 x（包括）之间的此类整数的数量，那么 a 和 b 之间的此类整数的数量可以由G(b) – G(a-1)给出。这是DP（动态编程）开始起作用的时候。所有满足上述性质的整数计数问题都可以通过数字DP方法解决。

例如：
问题：给定一个数 n，求从 1 到 n 的所有数的位数之和。
解法：

• 一个天真的解决方案是遍历从 1 到 n 的每个数字 x，并通过遍历 x 的所有数字来计算 x 中的和。下面是这个想法的实现
  

// A Simple C++ program to compute sum of digits in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;

int sumOfDigits(int );

// Returns sum of all digits in numbers from 1 to n
int sumOfDigitsFrom1ToN(int n)
{
        int result = 0; // initialize result

        // One by one compute sum of digits in every number from
        // 1 to n
        for (int x = 1; x <= n; x++)
                result += sumOfDigits(x);

        return result;
}

// A utility function to compute sum of digits in a
// given number x
int sumOfDigits(int x)
{
        int sum = 0;
        while (x != 0)
        {
                sum += x %10;
                x = x /10;
        }
        return sum;
}

// Driver Program
int main()
{
        int n = 328;
        cout << "Sum of digits in numbers from 1 to " << n << " is "
                << sumOfDigitsFrom1ToN(n);
        return 0;
}

• 我们可以通过找到一个模式来更有效地做到这一点（DP）
  

sum(9) = 1 + 2 + 3 + 4 ........... + 9
       = 9*10/2
       = 45

sum(99)  = 45 + (10 + 45) + (20 + 45) + ..... (90 + 45)
         = 45*10 + (10 + 20 + 30 ... 90)
         = 45*10 + 10(1 + 2 + ... 9)
         = 45*10 + 45*10
         = sum(9)*10 + 45*10

sum(999) = sum(99)*10 + 45*100

上面的公式是使用动态规划实现的，因为存在重叠的子问题。sum(n)求解思路
1) Find number of digits minus one in n. Let this value be 'd'.  
   For 328, d is 2.

2) Compute some of digits in numbers from 1 to 10d - 1.  
   Let this sum be w. For 328, we compute sum of digits from 1 to
   99 using above formula.

3) Find Most significant digit (msd) in n. For 328, msd is 3.

4) Overall sum is sum of following terms

    a) Sum of digits in 1 to "msd * 10d - 1".  For 328, sum of
       digits in numbers from 1 to 299.
        For 328, we compute 3*sum(99) + (1 + 2)*100.  Note that sum of
        sum(299) is sum(99) + sum of digits from 100 to 199 + sum of digits
        from 200 to 299.  
        Sum of 100 to 199 is sum(99) + 1*100 and sum of 299 is sum(99) + 2*100.
        In general, this sum can be computed as w*msd + (msd*(msd-1)/2)*10d

    b) Sum of digits in msd * 10d to n.  For 328, sum of digits in
       300 to 328.
        For 328, this sum is computed as 3*29 + recursive call "sum(28)"
        In general, this sum can be computed as  msd * (n % (msd*10d) + 1)
        + sum(n % (10d))C++算法实现：
// C++ program to compute sum of digits in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;

// Function to computer sum of digits in numbers from 1 to n
// Comments use example of 328 to explain the code
int sumOfDigitsFrom1ToN(int n)
{
        // base case: if n<10 return sum of
        // first n natural numbers
        if (n<10)
        return n*(n+1)/2;

        // d = number of digits minus one in n. For 328, d is 2
        int d = log10(n);

        // computing sum of digits from 1 to 10^d-1,
        // d=1 a[0]=0;
        // d=2 a[1]=sum of digit from 1 to 9 = 45
        // d=3 a[2]=sum of digit from 1 to 99 = a[1]*10 + 45*10^1 = 900
        // d=4 a[3]=sum of digit from 1 to 999 = a[2]*10 + 45*10^2 = 13500
        int *a = new int[d+1];
        a[0] = 0, a[1] = 45;
        for (int i=2; i<=d; i++)
                a = a[i-1]*10 + 45*ceil(pow(10,i-1));

        // computing 10^d
        int p = ceil(pow(10, d));

        // Most significant digit (msd) of n,
        // For 328, msd is 3 which can be obtained using 328/100
        int msd = n/p;

        // EXPLANATION FOR FIRST and SECOND TERMS IN BELOW LINE OF CODE
        // First two terms compute sum of digits from 1 to 299
        // (sum of digits in range 1-99 stored in a[d]) +
        // (sum of digits in range 100-199, can be calculated as 1*100 + a[d]
        // (sum of digits in range 200-299, can be calculated as 2*100 + a[d]
        // The above sum can be written as 3*a[d] + (1+2)*100

        // EXPLANATION FOR THIRD AND FOURTH TERMS IN BELOW LINE OF CODE
        // The last two terms compute sum of digits in number from 300 to 328
        // The third term adds 3*29 to sum as digit 3 occurs in all numbers
        //                         from 300 to 328
        // The fourth term recursively calls for 28
        return msd*a[d] + (msd*(msd-1)/2)*p +
                msd*(1+n%p) + sumOfDigitsFrom1ToN(n%p);
}

// Driver Program
int main()
{
        int n = 328;
        cout << "Sum of digits in numbers from 1 to " << n << " is "
                << sumOfDigitsFrom1ToN(n);
        return 0;
}
时间复杂度: O(len(N))
空间复杂度: O(len(N))
6.模式搜索

模式搜索算法有时也称为字符串搜索算法，并被视为字符串算法的一部分。这些算法在在另一个字符串中搜索一个字符串的情况下很有用。
6.1 朴素模式搜索

将模式逐一滑动到文本上并检查匹配。如果找到匹配项，则再次滑动 1 以检查后续匹配项。
// C++ program for Naive Pattern
// Searching algorithm
#include <bits/stdc++.h>
using namespace std;

void search(char* pat, char* txt)
{
        int M = strlen(pat);
        int N = strlen(txt);

        /* A loop to slide pat[] one by one */
        for (int i = 0; i <= N - M; i++) {
                int j;

                /* For current index i, check for pattern match */
                for (j = 0; j < M; j++)
                        if (txt[i + j] != pat[j])
                                break;

                if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
                        cout << "Pattern found at index "
                                << i << endl;
        }
}

// Driver Code
int main()
{
        char txt[] = "AABAACAADAABAAABAA";
        char pat[] = "AABA";
        search(pat, txt);
        return 0;
}

// This code is contributed
// by Akanksha Rai
最坏情况下的比较次数为 O(m*(n-m+1))
6.2 KMP算法

KMP 算法背后的基本思想是：每当我们检测到不匹配时（在一些匹配之后），我们已经知道下一个窗口文本中的一些字符。我们利用这些信息来避免匹配我们知道无论如何都会匹配的字符。
关于KMP算法详细内容参见另外一篇文章：https://zhuanlan.zhihu.com/p/479320454
// C++ program for implementation of KMP pattern searching
// algorithm
#include <bits/stdc++.h>

void computeLPSArray(char* pat, int M, int* lps);

// Prints occurrences of txt[] in pat[]
void KMPSearch(char* pat, char* txt)
{
        int M = strlen(pat);
        int N = strlen(txt);

        // create lps[] that will hold the longest prefix suffix
        // values for pattern
        int lps[M];

        // Preprocess the pattern (calculate lps[] array)
        computeLPSArray(pat, M, lps);

        int i = 0; // index for txt[]
        int j = 0; // index for pat[]
        while (i < N) {
                if (pat[j] == txt) {
                        j++;
                        i++;
                }

                if (j == M) {
                        printf("Found pattern at index %d ", i - j);
                        j = lps[j - 1];
                }

                // mismatch after j matches
                else if (i < N && pat[j] != txt) {
                        // Do not match lps[0..lps[j-1]] characters,
                        // they will match anyway
                        if (j != 0)
                                j = lps[j - 1];
                        else
                                i = i + 1;
                }
        }
}

// Fills lps[] for given patttern pat[0..M-1]
void computeLPSArray(char* pat, int M, int* lps)
{
        // length of the previous longest prefix suffix
        int len = 0;

        lps[0] = 0; // lps[0] is always 0

        // the loop calculates lps for i = 1 to M-1
        int i = 1;
        while (i < M) {
                if (pat == pat[len]) {
                        len++;
                        lps = len;
                        i++;
                }
                else // (pat != pat[len])
                {
                        // This is tricky. Consider the example.
                        // AAACAAAA and i = 7. The idea is similar
                        // to search step.
                        if (len != 0) {
                                len = lps[len - 1];

                                // Also, note that we do not increment
                                // i here
                        }
                        else // if (len == 0)
                        {
                                lps = 0;
                                i++;
                        }
                }
        }
}

// Driver program to test above function
int main()
{
        char txt[] = "ABABDABACDABABCABAB";
        char pat[] = "ABABCABAB";
        KMPSearch(pat, txt);
        return 0;
}
7.回溯算法

回溯是一种递归解决问题的算法技术，它通过尝试逐步构建解决方案，一次一个，删除那些在任何时间点都不能满足问题约束的解决方案。
例如，考虑 SudoKo 解决问题，我们尝试一个一个地填充数字。每当我们发现当前数字不能导致解决方案时，我们将其删除（回溯）并尝试下一个数字。这比简单的方法（生成所有可能的数字组合，然后一个接一个地尝试每个组合）要好，因为它在回溯时会丢弃一组排列。

例题：删除无效括号

将给出一个表达式，它可以包含左括号和右括号以及可选的一些字符，字符串中不会有其他运算符。我们需要删除最少数量的括号以使输入字符串有效。如果可能有多个有效输出删除相同数量的括号，则打印所有此类输出。

Input  : str = “()())()” -
Output : ()()() (())()
There are two possible solutions
"()()()" and "(())()"

Input  : str = (v)())()
Output : (v)()()  (v())()解法思路：
由于我们需要生成所有可能的输出，我们将通过删除一个左括号或右括号来回溯所有状态，并检查它们是否有效，如果无效，然后将删除的括号添加回去并进入下一个状态。
我们将使用 BFS 来移动状态，使用 BFS 将确保删除最少数量的括号，因为我们逐级遍历状态，并且每个级别对应于一个额外的括号删除。除了这个 BFS 不涉及递归，因此也节省了传递参数的开销。
/* C/C++ program to remove invalid parenthesis */
#include <bits/stdc++.h>
using namespace std;

// method checks if character is parenthesis(open
// or closed)
bool isParenthesis(char c)
{
        return ((c == '(') || (c == ')'));
}

// method returns true if string contains valid
// parenthesis
bool isValidString(string str)
{
        int cnt = 0;
        for (int i = 0; i < str.length(); i++)
        {
                if (str == '(')
                        cnt++;
                else if (str == ')')
                        cnt--;
                if (cnt < 0)
                        return false;
        }
        return (cnt == 0);
}

// method to remove invalid parenthesis
void removeInvalidParenthesis(string str)
{
        if (str.empty())
                return ;

        // visit set to ignore already visited string
        unordered_set<string> visit;

        // queue to maintain BFS
        queue<string> q;
        string temp;
        bool level;

        // pushing given string as starting node into queue
        q.push(str);
        visit.insert(str);
        while (!q.empty())
        {
                str = q.front(); q.pop();
                if (isValidString(str))
                {
                        cout << str << endl;

                        // If answer is found, make level true
                        // so that valid string of only that level
                        // are processed.
                        level = true;
                }
                if (level)
                        continue;
                for (int i = 0; i < str.length(); i++)
                {
                        if (!isParenthesis(str))
                                continue;

                        // Removing parenthesis from str and
                        // pushing into queue,if not visited already
                        temp = str.substr(0, i) + str.substr(i + 1);
                        if (visit.find(temp) == visit.end())
                        {
                                q.push(temp);
                                visit.insert(temp);
                        }
                }
        }
}

// Driver code to check above methods
int main()
{
        string expression = "()())()";
        removeInvalidParenthesis(expression);

        expression = "()v)";
        removeInvalidParenthesis(expression);

        return 0;
}
8.分而治之

分而治之是一种算法范式。典型的分治算法使用以下三个步骤解决问题。

• 划分：将给定问题分解为相同类型的子问题。
  
• 征服：递归解决这些子问题
  
• 组合：适当组合答案
  

以下是一些遵循分治算法的标准算法。  

• 快速排序是一种排序算法。该算法选择一个枢轴元素并重新排列数组元素，以便所有小于所选择的枢轴元素的元素都移动到枢轴的左侧，所有更大的元素都移动到右侧。最后，该算法递归地对枢轴元素左右的子数组进行排序。
  
• 归并排序也是一种排序算法。该算法将数组分成两半，对它们进行递归排序，最后将排序后的两半合并。
  
• 最近的点对 问题是在 xy 平面的一组点中找到最近的点对。通过计算每对点的距离并比较距离以找到最小值，可以在 O(n^2) 时间内解决该问题。分治算法在 O(N log N) 时间内解决了这个问题。
  
• Strassen 算法是一种将两个矩阵相乘的有效算法。将两个矩阵相乘的简单方法需要 3 个嵌套循环并且是 O(n^3)。Strassen 算法在 O(n^2.8974) 时间内将两个矩阵相乘。
  
• Cooley-Tukey 快速傅里叶变换 (FFT) 算法是最常见的 FFT 算法。它是一种分治算法，在 O(N log N) 时间内工作。
  
• 用于快速乘法的 Karatsuba 算法最多将两个n位数字
  

9.数学算法

10.几何算法

11.按位算法

12.图数据结构和算法

13.随机算法

14.分支定界算法