알고리즘

분류

자세한 것은 알고리즘을 참고하라.
문서설명
전수 검색 Brute force search. 자명한 검색알고리즘으로 그냥 집합의 모든 원소들을 하나씩 확인해 가면서 찾는 방법. 굳이 검색 알고리즘이 아니더라도, 아무 방법 없이 모든 해 공간을 탐색하는 경우에도 전수(brute force)라는 말을 쓴다. 물론 그 시간복잡도는 n개 원소에 대해서 평균 및 최악의 경우 O(n).
유클리드 알고리즘 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)…

목록

문서설명
정렬 알고리즘 정렬 문제, 즉 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…

세부 분류


도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기