演算法導入、ソート、データ構造、ハッシュ

培訓 - 1 演算法導入 ソート データ構造 ハッシュ 演算法導入 ソート データ構造 ハッシュ momohuang c2251393 chiangyo September 23, 2013 1 Schedule of the Year 1.1 Major Competition 9 12 11 10 12 10 TOI 的最 3 TOI 3 TOI 100 20 4 TOI 30 12 5 TOI 12 4 算 7 IOI 2014 1.2 Minor Competition 11 10 的 的 11 NPSC 複 12 PK 的話 的 的 USB I

1.3 Online Contests 演算法導入 ソート データ構造 ハッシュ 1.3 Online Contests codeforces.com 排 排 usaco.org 11 的 codechef.com 比 題 的 題 topcoder.com 較 複雜 算法 的比 1.4 Online Judges SGU acm.sgu.ru 的 OJ 題 POI main.edu.pl/en 訓 的 OJ 的題 URAL acm.timus.ru OJ POJ poj.org 題 題 題 TIOJ 218.210.35.237:8080/JudgeOnline tmt514 的 OJ HOJ hoj.twbbs.org/judge/ hanhan0912 的 OJ 題 xd 1.5 Online Courses Coursera 最 的 MOOC Stanford 的 Andrew Ng CS 的 edx MIT Harvard 的 MOOC CS Udacity 較 II

1.6 Recommended Books 演算法導入 ソート データ構造 ハッシュ 1.6 Recommended Books 培 的 的 題 算法 算法 Introduction to Algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 2 Introduction to Algorithm Competitions 2.1 What Is Big-O? f(x) = O(g(x)) as x 的 的 f(x) g(x) is bounded for all sufficiently large x x 0, M R +, s.t. x > x 0 R, f(x) g(x) < M f(x) = O(g(x)) x 的 order of f(x) order of g(x) x 3 = O(x 4 ) x 1000 = O(1.2 x ) 10000 x 4 = O(x 4 ) log x = O(x 0.007 ) o 的 f(x) = o(g(x)) as x o f(x) lim x g(x) = 0 O o < 0.00000012 x 2 = o(x 2 ) 的 於 0 III

2.1 What Is Big-O? 演算法導入 ソート データ構造 ハッシュ 於 的 Landau 的 x 於 2 x, x 4, log x 於 的 度 的 x 4 becomes infinite in higher order of x 3 話 x4 於 x 3 x α becomes infinite in higher order of x β α > β x α 的 order of magnitude α 的 法 的 order of magnitude 題 α > 0 ex 於 α > 0 log x 於 0 法 x α x α 的 order of magnitude 法 的話 <, > O o x 的 x x 0 f(x) = O(g(x)) as x x 0 f(x) = o(g(x)) as x x 0 ϵ, M R +, s.t. x x 0 < ϵ, f(x) g(x) < M f(x) lim x x 0 g(x) = 0 1 cos x = o(x) as x 0 f(x + h) f(x) = hf (x) + o(h) as h 0 x x 0 h 的 f(x + h) f(x) hf (x) 的 於 h x 的 O 的 IV

2.2 2.2 The Martial Arts of Problem演算法導入 ソート データ構造 ハッシュ Solving The Martial Arts of Problem Solving mo n 題的 題 mo n da i mo n su ta 算 遭遇到一 問スター WIN LOSE WIN LOSE WIN LOSE WIN 基 算法 的 題 if V for 的 的題

2.3 Some Problems 演算法導入 ソート データ構造 ハッシュ 2.3 Some Problems 1. <SGU 126> 題 1 A 2 B A + B < 2147483648 1 2 2 的 最 -1 2. <no judge pure thinking> 題 A = 3 (3(3...))}n B = 9 (9(9...))}m m n 最 A 於 B (n, m 10 6 ) 3. <no judge pure thinking> 題 比 N A 的 最 B 的 PK 的 lose N, A, B 1000 4. <no judge pure thinking> 題 的 A + B A B 的 最 5. <POI18 Party> 題 3n 2n 的 題 n n n n 1000 6. <Codeforces 197A> 題 比 A B 的 R 的 A, B, R 100 7. <Codeforces 297A> 題 01 的 A B A 的 A 的 1000 10001 1001 10010 A 的 A B A, B 度 1000 VI

3. 排序演算法導入 ソート データ構造 ハッシュ 3 排序 3.1 Introduction 排序 算法 排序 題 : N 的 ( 比較 的 ) 題的 法 算法 的 算法 的 3.2 O(N 2 ) 的算法 3 sort sort 的 外 的 排 的序 1. Selection sort O(N) 的 排序 的序 的最 O(1) 排序 的序 的 於 N 複雜度 的 O(N 2 ) 算 的 sort 2. Insertion sort O(N) 排序 的序 ( ( ) 比 的 wwww) 序 排 ( O(1) ) 最 O(N 2 ) O(N) 排序 的序 3. Bubble sort 最 ( i i+1 ) Selection sort 算法 比 Selection sort 3.3 O(NlgN) 的算法 的 比 O(N 2 ) 的排序法 的 (?):O(N lg N) 排序法 3 sort Heap sort 外的 sort 的 O(N 2 ) 的 Divide & Conquer 算法 的排序法 話 序 排序 VII

3.4 題外話 : 基於比較的排序的最低複雜度演算法導入 ソート データ構造 ハッシュ 1. Merge sort 序 排序 的 法 Selection sort 的 法 最 排序 的序 O(N 2 ) O(N) 排序的最 O(1) 比 序 的最 比較 的 O(1) O(N) 複雜度 T (N) = 2 T ( N ) + O(N) = O(N lg N) 算 2 O(N) O(lg N) 複雜度 = O(N) O(lg N) = O(N lg N) 2. Quick sort Merge sort Quick sort (Pivot) 比較 的 的 比較 的 的 O(N) ( ) 排序 算法最 的 複雜度 Merge sort O(N lg N) 的 最 ( 最 ) 複雜度 T (N) = T (N 1) + O(N) = O(N 2 )( N O(N)) 法算 的 Quick sort 複雜度 Θ(N lg N) Quick sort 的 度的 Insertion sort 的 法 STL 的 std::sort() 的 Quick sort(intro sort) 3. Heap sort 算法的 的 最 的 Heap O(lg N) O(1) 最 O(lg N) 最 Heap 的培訓 3.4 題外話 : 基於比較的排序的最低複雜度 的最低複雜度 排序 序 最 的最低複雜度 ( Insertion sort O(N) ) N 排序 的 N! ( ) 比較 的 N! 2! m 比較 的 N! (2!) m N! (2!) m 1 的 於 排序的 m = O(lg N!) = O(N lg N) 最 比較的 於 O(N lg N) VIII

3.5 O(N + C) 的算法演算法導入 ソート データ構造 ハッシュ 3.5 O(N + C) 的算法 的 sort 基於比較的排序 算法 基於比較的排序 算法! 基於比較的 算法 複雜度 的 1. Counting sort (index ) 的 複雜度 O(N +C) C 2. Radix sort 排 法 的 排序 ( Counting sort) 複雜度 O((log B C) (N + B)) B 法 C 3.6 Exercises!! 的算法 排序 算法的題 排序算法 排序 法 排序算法的 1. 序 (TIOJ 1080) N( 10 5 ) 的 a (i, j) : i < j a i > a j 2. K (TIOJ 1364) 度 N 的 K O(N) K 3. Bubble sort 算 算 度 N( 10 5 ) 的 Bubble sort 排序的 4. Comiket(TIOJ 1410) N( 10 5 ) Loli i Loli s i 的 ti 的 最 的 最 Loli IX

4. Data Structure 演算法導入 ソート データ構造 ハッシュ 4 Data Structure Introduction 的 算 度 的 題 複雜 題的 的 算法的 的 的 法 的 題 的 4.1 Array 的 法 的 的 O(1) O(n) ( ) 4.2 Linked List linked list 的 的 insert erase 法 O(1) O(n) linked list (data node) 的 pointer 的 pointer 的 NULL 外 的 doubly linked list 的 pointer 的 pointer 4.3 Stack LIFO 的 stack push pop push stack 的 pop stack 的 於 "last in, first out" 的 的 的 DFS 的 4.4 Queue FIFO 的 queue enqueue dequeue enqueue queue 的 dequeue queue 的 於 "first in, first out" 的 的 ( stack ) 排 的 排的 BFS 的 X

4.5 Deque 演算法導入 ソート データ構造 ハッシュ 4.5 Deque "deck" double-ended queue 的 enqueue dequeue 4.6 Tree tree (node) (child) (parent) (root) 的 (leaf ) (binary tree) " 0 2 " 的 tree 的 排序 的 O(logn) 的 4.7 Heap heap 的 insert extract insert heap extract heap 最 ( 最 ) 的 heap 的 比較 的 insert extract O(logn) 4.8 Conclusion STL 的 stack queue deque priority_ queue 的 的 stack queue deque heap STL 的 題 4.9 Exercises 1. <Uva 514 Rails> A 1, 2, 3,... n 的 序 station 1 n 的 排 station 度 的 排 序 2. <TIOJ 1176 Cows> 度 n 的 於 的 比 的 的 3. <STEP5 0098 > 法 XI

5. Hash 演算法導入 ソート データ構造 ハッシュ 4. <TIOJ 1063 最 > n m 的 01 1 的最 5. <TIOJ 1489 > 最 a z 的 6. <STEP5 0038 的 > 度 n 的 序 A, B (n < 100000) 1. stack push& pop 的 A B? 2. 序 C A 的 法 C B 法? 序 C "-" 7. <STEP5 0020 > 的 n (4 n 5 10 5 ) 8. <HOJ 2 > N [X i, Y i ] [X a, Y a ], [X b, Y b ] X a < X b < Y a < Y b ( ) 9. <TIOJ 1637 > 的 a, b 的 度 於 a, b 度? 5 Hash Introduction n 最 的 法 序 O(n) 排序 binary search 低 O(logn) 的 " 的 " 的 n 1 的 x 序 的 x 的 序 的話 的複雜度 O(1) x 的 x 的 x 的 雜 (hash) 的 ( ) ( ) 的 XII

5.1 Hash Function 演算法導入 ソート データ構造 ハッシュ 雜 (hash function) 的 雜 (hash table) x x 雜 雜 的 x 雜 的雜 5.1 Hash Function 雜 的 L 的雜 h(x) X 0 L 1 的 的雜 法 的 hash 的雜 低 雜 5.1.1 Hash h(x) = x 法 h(x) x 的 法 L 於 X 5.1.2 Mod Hash 雜 mod L hash h(x) = x mod L h(x) = x k mod L 的 h(x) 雜 的 5.2 Collision 的 法 5.2.1 RP 的 的雜 5.2.2 Chaining 的 linked list 5.2.3 Linear Probing 的雜 h(x, i) = (h(x) + i) mod L i 0 h(x, i) 外 Quadratic Probing h(x, i) = (h(x) + c 1 i 2 + c 2 i) mod L XIII

5.3 std::map 演算法導入 ソート データ構造 ハッシュ 5.2.4 Doubly Hashing 的雜 h(x, i) = (h 1 (x) + i h 2 (x)) mod L 5.2.5 Perfect Hashing 雜 題 複雜度 O(n) 雜 雜 雜 h 1 (x) 雜 於 hash 的 的雜 h 2 (x) 雜 hash 雜 h 2 (x) 5.3 std::map map STL 的 (associative container) key value mapped value 於 的雜 5.4 Exercises 1. <TIOJ 1160 題 > n k 最 的 (0 n 100000) XIV