运筹学笔记
秋运筹学(陈士祥)学习笔记。
突然在 U 群里爆出了这题,回想起了这道当时自己感觉挺有趣的一题,过来写篇题解。
Pseudorandomness learning notes.
Pseudorandomness Chapter 6 learning notes.
In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.
一种可以在 O(mlog∣f∣(m+nlogn)) 时间复杂度内求解最大流的诡异方法,其中 ∣f∣ 是最大流流量。方法名称是我自己胡乱翻译的,原名叫:The Fattest Augmenting Path Heuristic。
论文 A Lower Bound on the Size of Shellsort Sorting Networks. Robert Cypher, 1989 阅读笔记。这篇文章证明了基于单调递减间隔序列的希尔排序的时间复杂度均为 Ω(nlog2n/loglogn)。