170627(화) - Stanford Engineering's Algorithms (Divide & Conquer Algorithms)

Divide & Conquer Algorithms

1. DIVIDE 

into smaller sub problems

2. CONQUER

via recursive calls

3. Combine

solutions of sub problems into one to the original problems

O(nlogn) Algorithms for counting inversions

n개의 수 중에서 2개를 뽑는 경우의 수

---

---

Euclidean distance

- 두 점 사이의 거리를 계산할 때 쓰이는 방법

- 이 거리를 이용하여 유클리드 공간을 정의 가능

- 이 거리에 대응하는 노름을 유클리드 노름이라고 한다.

두 점 A(x1,y1), B(x2,y2)사이의 거리

     d=(x2−x1)2+(y2−y1)2−−−−−−−−−−−−−−−−−−√