Quicksort
2018-04-21
Algorithm
2023
Time Complexity
With partition, the elements compared each time are as follow:
n, n/2, n/2, n/4, n/4, n/4, n/4, ..., 1, 1, ..., 1 (n ones)
And their sum is:
n, n, n, ..., n
But how much n?
Since n is divided to 1 by 2, there sure is log2(n) number of n.
So the time complexity is: n*log2(n)
Unique-elements sorting implement
From Quicksort - wikipedia:
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop
莫比乌斯反演
2017-10-25
Algorithm
336
Introduction
最精彩的证明是自动证明。今天在知乎上看到的一位大佬对莫比乌斯反演的证明让我体会到了数论的神奇。坚定了我投靠数学的决心。
Mobius Inversion Formula
若存在
则有
反之亦然。
Basic Concept
1. Convolution / 卷积
对两个数论函数, , 卷积运算定义为
卷积运算满足：
交换律：
结合律：
存在单位元. . 不难知道定义应为：
2. 乘法单位元
普通乘法意义上的单位元，将所有自然数映射到1的函数，记为。
3. 莫比乌斯函数
在卷积意义下的逆元，称为莫比乌斯函数。即
展开写作：
定义为：
在知乎上大神引用的定义是：
这两种定义是等价的。前者是英文 Wikipedia 上给出的定义。后者可能比较好理解一些。
Prove
莫比乌斯反演写作卷积形式：
证明：
反之
Reference
参考资料：
[1] 知乎 - 如何证明莫
