ql213
- 浏览: 11462 次
- 性别:
- 来自: 成都
-
最新评论
文章列表
给定n个元素，要求解其中第k小的元素，一般采用先排序后然后直接得结果的过程。在数据量小的情况下没问题，时间复杂度是O(n*logn). 但是当数据量非常大的时候就要考虑是否有更好的算法来代替全局排序。
这里，采用剪枝策略，即如果要在线性时间内得到问题的解，必须在每次迭代的过程中用O(n)的时间剪去部分元素，使得在下次迭代过程中不参与比较。
《算法设计与分析导论》一书给出了一个比较经典的线性时间复杂度下的求解算法。
核心思想：
我们以每5个元素为子集划分源数组，然后对每个子集排序求出中位数，这样的中位数集合组成一个新的序列M，对M递归的求解其中位数p，得到的p即为划分点。p将源 ...
对于单源最短路径问题，可以利用贪心策略求解，其经典算法便是Dijkstra算法。首先找出与v0点最邻近点的最短路径，然后找出与v0点第二近顶点的最短路径，直到找到最后一个点与v0的最短路径。
实现Dijkstra算法可以和prim算法类似，需要构造2个集合s1,s2。其中s1是当前搜索到的最短路径顶点集，s2是剩下的带求解的点集。每一次搜索都会将s2中的点与最后加入到s1的点进行权值更新操作，一旦发现有s1到s2的更短的路径，就更新目前的距离集合，并且将最短距离对应的那个点加入到s1中，并从s2中删除。
Dijkstra算法的时间复杂度是O(n^2)。
import ja ...
在上一篇中，我们提到了用来求解边数不是特别多的（例如完全图）生成最小生成树的Kruskal算法。对于稠密图，Kruskal算法的效率不高，这时候我们可以用同样经典的Prim算法求解最小生成树问题。
Prim算法的核心思想是按照当前点集到还未加入的点集的最短边来加入新的点，直到加入n个点来得到最小生成树，设无向连通图有n个顶点。
Prim算法一般包含如下重要步骤：
1. 任意选定一个初始点作为当前点集
2. 求当前点集到还未加入的点集的最短边，并把对应的点加入到当前点集--时间复杂度是 O(n^2)
由此看出，Prim算法总的时间复杂度主要由求点集间最短 ...
最小生成树问题是贪心策略的经典应用，其中Kruskal算法用来求解边数不是特别多的（例如完全图）图的最小生成树。这里我们以无向连通图为例。
Kruskal算法的核心思想是按照边的从小到大的顺序依次加入到点集中，直到加 ...
求解动态规划问题的核心在于找准阶段与阶段之间的状态变化规律，从而制定状态转化的决策，由上一阶段的所有局部最优状态值推出下一阶段的局部最优，进而推出全局最优。 在求解问题的时候，我们通常要构造一个二维数组，用来保存当前得到的局部最优值，这样在推导下一阶段的最优值的时候就可以利用上一阶段得到的结果求解，而这显然比穷举更高效。 记住动态规划的一个思想：许多当前的局部最优看不见未来的最优，但是未来的最优一定包含当前的某个局部最优。
以某年的信息学竞赛为例，题目大意如下： 在一个长为N的数字字符串s中插入r个乘号，将s拆分成r+1部分，求其最大乘积。 思路： 该题目可以用动态规划的思想求解，因为 ...