SkyWT

我们的征途是星辰大海。

(转)八大排序算法稳定性分析

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

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

各排序算法的稳定性:

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

Read more...

OI学习OI算法

高斯消元入门

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

解多元方程组特别方便。

Read more...

数位 DP 入门:HDU 3555 Bomb

简单来说,数位 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...

主定理与递归程序时间复杂度的计算

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

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

Read more...

OI学习OI算法

斜率优化小结

在一维线性动态规划里,我们经常见到形如 $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...