을 참고하라.
| 문서 | 설명 |
| 유클리드 알고리즘 |
Euclidean algorithm. 두 자연수의 최대공약수를 구하는 알고리즘. 기원전 300년 경에 유클리드의 《원론》에서 처음 기술되었으며 아마 그 이전에도 알려져 있었을 것으로 추측된다. 따라서 가장 오랫동안 살아 남은 알고리즘이라 할 수 있는데, Donald Knuth는 TAOCP에서 이 알고리즘을 "모든 알고리즘의 할아버지"라고 부르기까지 한다.k > 0a > 0\gcd(ka,a) = aa > b > 0\gcd(a,b) = \gcd(a-b,b)\gcd(a,b) = \gcd(b,a)\gcd\gcd(a,0) = \gcd(0,a) = a\gcd(a,b) = \gcd(a \mod b,b)a > b\gcd(a,b) = \gcd(b,a \mod b)O(\log \min\{a,b\})O\left((\log \min\{a,b\})^2\right)… |
| 전수 검색 |
Brute force search. 자명한 검색알고리즘으로 그냥 집합의 모든 원소들을 하나씩 확인해 가면서 찾는 방법. 굳이 검색 알고리즘이 아니더라도, 아무 방법 없이 모든 해 공간을 탐색하는 경우에도 전수(brute force)라는 말을 쓴다. 물론 그 시간복잡도는 n개 원소에 대해서 평균 및 최악의 경우 O(n). |
| 문서 | 설명 |
| 정렬 알고리즘 |
정렬 문제, 즉 n개의 원소가 들어 있는 배열을 잘 섞어서 순서대로 배치하는 문제를 푸는 알고리즘. 전산학에서 매우 중요한 문제로 취급받기 때문에 전산학 전공했는데 이걸 모른다고 하는 사람이 있으면 그 사람이 사기꾼일 가능성을 의심해 봐야 한다.Aa_1, a_2, \cdots, a_n \in A\le\, \subseteq A \times A\pi\mathrm{S}_na_{\pi(1)} \le a_{\pi(2)} \le ... \le a_{\pi(n)}i \ne j \implies (a_i \le a_j \wedge a_j \le a_i)A\le\mathrm{O}(n \log n)\vert \mathrm{S}_n \vert = n!\le\log_2 n!n \log n\mathrm{O}(n^2)\mathrm{O}(n \log n)\mathrm{O}(kn)k\mathrm{O}(n \log^2 n)\mathrm{O}(n^{\frac{\log 3}{\log 2}})\le\mathrm{O}(n… |
