>

字数 561 阅读 12 评论 6

Big-O notation

GCD

Greatest Common Divider

gcd(a, b) = the greates number g where g/a and g/b

1. Euclid’s algorithm

欧几里德算法又称辗转相除法，用于计算两个整数 a,b 的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a, b) = gcd(b, a mod b)

证明：a 可以表示成 a = kb + r_，则 _r = a mod b
假设 d 是 a,b 的一个公约数，则有 d|a, d|b_，而 _r = a - kb_，因此 _d|r
因此 d 是 (b,a mod b) 的公约数

假设 d 是 (b,a mod b) 的公约数，则 d | b, d |r_，但是 _a = kb +r
因此 d 也是 (a,b) 的公约数

因此 (a,b) 和 (b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

欧几里德算法就是根据这个原理来做的，其算法用 C++ 语言描述为：

1
2
3
4
5
int Gcd(int a, int b){
    if(b == 0)
        return a;
    return Gcd(b, a % b);
}

2. Stein algorithm

欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

Stein 算法由 J. Stein 1961 年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是，Stein 算法只有整数的移位和加减法，这对于程序设计者是一个福音。

为了说明 Stein 算法的正确性，首先必须注意到以下结论：

gcd(a,a) = a，也就是一个数和他自身的公约数是其自身
gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当 k=2 时，说明两个偶数的最大公约数必然能被 2 整除。

Prime Number & Divisibility os Numbers

Sorting

  • Topological Sorting
  • Binary Search
  • Depth/Breadth First Search

Tree traversal

Recursion

Greedy Algorithm

Divide and Conquer

Dynamic Programming (Advanced Dynamic Programming)

Shorted Path

Sieve of Eratosthenes

  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall

Classic Problems

  • Lowest Common Ancestor, LCA
  • Longest Common Path, LCP

Three level of algorithm depends on the difficulties:

Basic

  • Brutal Force Search
  • Greedy Algorithms
  • Data Structures (Array, LinkedList, Binary Tree, Stack/Queue, Map, etc.)
  • DFS & BFS

Intermediate

  • Binary Search
  • Dynamic Programming
  • Divide & Conquer
  • Branch Bound

Advanced

  • Number Theory
  • Game Theory
  • Graph Theorem
    • Shortest Path
    • Max Flow
    • Bipartite