SkyWT

Welcome!

转自知乎:八大排序算法稳定性分析,原来稳定性是这个意思……
这是 €€F 非常喜欢的排序稳定性分析……

稳定性定义: 排序前后两个相等的数相对位置不变,则算法稳定。
稳定性的好处: 从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。

各排序算法的稳定性:

  1. 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法;
  2. 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

Read more...

发布 0 条评论

\begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix}

每增加一个维度,世界便会增加无限的美感。

Read more...

发布 0 条评论

数学上,高斯消元法(Gaussian Elimination),是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个行梯阵式。

解多元方程组特别方便。

Read more...

发布 0 条评论

简单来说,数位 DP 大概就是把一个数字拆开按位进行 DP 的一种思想。

HDU 3555 Bomb

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Read more...

发布 0 条评论

主定理可以用来分析递归算法的时间复杂度(也叫渐进复杂度)。在以前,我们知道快速排序的时间复杂度是 \Theta (N \ast \log_2 N ) ,我们也知道它不稳定,但是我们仿佛不知道这个 \Theta (N \ast \log_2 N ) 是怎么来的……学习了主定理,我们就可以证明了~

这个“主定理”名字真的十分霸气:Master Theorem……

Read more...

发布 0 条评论

之前已经介绍过,网络流中最大流就是满足网络流的三个限制前提下,源点到汇点的最大流量,可以用 Edmonds-Karp 算法或者 Dinic 算法求解。
网络流的一个割,定义为对所有点集的一个二划分(就是划分为两个点集),使得源点和汇点处于不同的点集中。假设源点 s 在点集 S 中,汇点 t 在点集 T 中,割集就是这两个点集中的点分别连的边,也就是 (u,v),u\in S,v \in T。最小割就是使割集内边权和最小的割集。
下面我们要证明一个结论:网络流的最小割容量=最大流量。

Read more...

发布 0 条评论

在一维线性动态规划里,我们经常见到形如 f(i)=min/max(f(j)+c_i)(其实可以看成 f(i)=min/max(a_i+b_j) )这样形式的转移方程。朴素做法是 \Theta (N^2)。显然这样的形式可以用单调队列维护,优化到 \Theta (N)。但是如果遇到 f(i)=min/max(a_i\ast b_j+c_i+d_j) 这样的,似乎用单调队列就难以维护了……因为 a_i\ast b_j 既与 i 有关,又与 j 有关。这时候就要用到另一种优化方式:斜率优化。

Read more...

发布 0 条评论