算法概念性知识

本文主要介绍一些经典算法的概念性知识，以及对算法思想的一些理解，不涉及任何具体的代码实现。

算法的相关概念

算法的定义：它是若干指令的有穷序列。有以下性质

• 输入：有外部提供的量作为算法的输入。
• 输出：算法至少产生一个量作为输出。
• 确定性：组成算法的每条指令是清晰的、无歧义的。
• 有限性：算法中的每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

程序的定义：它是算法用某种程序设计语言的具体实现，可以不用满足有限性的性质。

算法复杂性

5个渐进性分析记号$O$、$\Omega$、$o$、$\omega$、$\theta$，假设对所有的$n(n>0)$，都有$f(n)\geq0$，$g(n)\geq0$。

渐进上界记号$O$

定义：$O(g(n))=\{f(n)|$存在正常数$c$和$n_0$使得对所有$n\geq n_0$有：$0 \leq f(n) \leq cg(n)\}$，则称函数$f(n)$当$n$充分大时有上界，且$g(n)$是它的一个上界，记为$f(n)=O(g(n))$，又称为$f(n)$的阶不高于$g(n)$的阶。

渐进下界记号$\Omega$

定义：$\Omega (g(n))=\{f(n)|$存在正常数$c$和$n_0$使得对所有$n\geq n_0$有：$0 \leq cg(n) \leq f(n)\}$，则称函数$f(n)$当$n$充分大时有下界，且$g(n)$是它的一个下界，记为$f(n)=\Omega (g(n))$，又称为$f(n)$的阶不低于$g(n)$的阶。

递归

递归算法是直接或间接调用自身的算法。

递归函数不一定能用非递归的方式实现。

斐波那契数列既可以用递归实现，也可以用非递归实现。

递归算法容易定义，结构清晰，但运行效率较低，一般情况下，耗费的计算时间和存储空间都要比非递归算法多。

分治

分治法的基本思想是将规模较大的问题划分为规模较小的子问题来求解。

二分搜索算法的前提是数据有序。

用分治法求解大整数乘法和Strassen矩阵乘法的基本思想是通过合理的变换运算来减少乘法的次数。

合并排序和快速排序的平均时间复杂性均为$O(nlogn)$。

动态规划

动态规划也是将规模较大的问题划分为规模较小的子问题来求解，但与分治法不同的是，动态规划所划分出来的子问题相互不独立。

动态规划算法适用于求解最优化问题，一般采用自底向上的方式来计算。

自底向上和自顶向下的根本区别是：自底向上的分析，是从具体到抽象；自顶向下的分析，是从抽象到具体。

参考https://www.cnblogs.com/Qsir/p/5838802.html

动态规划求解的问题也可以用递归算法求解，但是可能会造成重复计算和不必要的资源耗费。

动态规划求解的问题具有最优子结构和重叠子问题性质。

利用动态规划求解矩阵连乘问题时，其渐进时间复杂度为 $O(n^3)$ ($n$表示矩阵个数)。

使用动态规划求解最优二叉搜索树的时间复杂度为$O(n^3)$，$n$是序列元素数量。

动态规划求解0-1背包问题时，其时间复杂度是伪多项式。

关于伪多项式时间算法可参考algorithm - What is pseudopolynomial time? How does it differ from polynomial time?

使用动态规划算法求解2个长度为$n$的序列的最长公共子序列的时间复杂度为$O(n^2)$。

贪心

贪心算法可能存在多个贪心策略，具有最优子结构的性质，常常使用堆结构存储数据。

求解活动安排问题 的贪心算法GreedySelector的时间复杂性为$O(nlogn)$，对活动进行结束时间的非减排序后，再使用GreedySelector求解的时间复杂度为$O(n)$。

哈夫曼编码是一种最优前缀码，其时间复杂度为$O(nlogn)$，其各字符的编码不一定唯一。

当有多个权重相等的字符时，其在哈夫曼树中的位置不唯一，它可以是左子树也可以是右子树，即字符可能存在多种编码情况。

哈夫曼编码只是保证平均查找码长最小，但平均查找码长最小的编码组合不一定唯一。

对于给定的一个带权有向图$G=(V,E)$，无法使用Dijkstra算法求解出其最短路径，因为Dijkstra无法处理带负权图。可以使用Bellman-Ford算法求解，不过Bellman-Ford是基于动态规划设计的。

Dijkstra算法无法处理有负边的问题，只适用于无负权图，参考dijkstra算法为什么不能有负边？

这种“负边问题”也是贪心算法本身的缺陷。

Dijkstra是以点为单位进行操作，Bellman-Ford是以边为单位进行操作。

关于Bellman-Ford算法可以参考Bellman-Ford与SPFA

0-1背包问题不一定能用贪心算法得到最优解 ，背包问题(可散装)的贪心算法也就不适用于0-1背包问题，可能导致背包无法装满。

时间复杂性表达式分析

对于$T(n)=2T(n/2)+n$，$T(0)=T(1)=1$，(这种表达式正好就是快速排序的时间复杂性表达式)

以下说法是正确的，$T(n)=O(n^2)$、$T(n)=\theta (nlogn)$、$T(n)=O(nlogn)$

以下说法是错误的，$T(n)=\Omega (n^2)$，应为$T(n)=\Omega(nlogn)$

关于$O$、$\theta$、$\Omega$可以类比为高阶、同阶、低阶。

NP完全理论

P类问题：所有可以在多项式时间内求解的判定问题。例如，冒泡排序、快速排序、最短路径等。

NP问题：无法确定具体的多项式时间，但是对于它的解可以在多项式时间内验证。例如，超大规模的数字计算，可能无法在短时间内求解，但是可以假设一个解并在短时间得到验证。

NPC问题：也称NP完备问题，这类NP完备问题如果能在多项式时间内解决，那么NP中的每一个问题都可以在多项式时间内解决，即所有NP类问题都可以在多项式时间内规约到某个NPC问题。

但是目前尚未得到一个NP完备问题的多项式时间算法。

P类问题和NP问题，都可在多项式时间内求解，不同的是NP问题是非确定性的。

第一个NPC问题是SAT布尔可满足性问题，又由Cook提出。

排序相关

对于有序数组再排序，比较次数最少的是插入排序。

图相关

对于任意无向连通图$G=(V,E)$，当$G$采用邻接矩阵存储时，关于其最小生成树

• 图$G$的最小生成树是不唯一的
• 对于图$G$可以采用$Prim$算法或$Kruskal$算法来求解其最小生成树
• $Prim$算法的复杂度为$O(n^2)$，$n$为图中顶点的数量
• $Kruskal$算法的复杂度为$O(eloge)$，$e$为图中边的数量

线性时间选择

线性时间查找最小的元素或者第$k$小的元素最少也要$O(n)$的时间复杂度，即遍历整个元素集合的时间复杂度。

使用线性时间选择Select算法求解，只有在元素已经有序的前提下，其时间复杂度才为$O(logn)$。

当$k\leq nlogn$或$k\geq n-nlogn$时，使用堆排序可能在$O(n)$的时间复杂度内求解。

最优装载问题

最优装载问题就是0-1背包问题的一个变形。

对于最优装载问题，一定存在一组可行解。

最优装载问题，使用贪心算法来求解，自然有最优子结构的性质。

最优装载问题的贪心策略是选择重量最轻的集装箱先装。

散装背包问题

散装背包问题使用贪心算法求解，其时间复杂度为$O(nlogn)$。

硬币称重问题

8个硬币中，已知其中一个硬币很重，使用最少的次数找出这枚硬币。

常见的错误思路：4,4 —> 2,2—>1,1

每次对半称，找重的一边，以此类推，共需要3次。

一种更好的思路：3,3…2 —> 1,1…1 或 1,1

先取6枚硬币对半称，余下2枚硬币。分情况讨论

• 3,3对称不平衡，硬币在重的一边的3枚硬币中。

  在3枚硬币中，再取2枚硬币对称就可以直接求解。

  • 若不平衡，则硬币就是重的一边的硬币
  • 若平衡，则硬币就是未称量的那一枚硬币

• 3,3对称平衡，硬币在余下的2枚硬币中。

  直接称量余下的2枚硬币，即可求解。

以上两种情况所需的次数均为2次。

参考

https://www.bilibili.com/video/BV1Ga4y1G7Q8