양자 알고리듬 (Quantum Algorithm) 편집하기 (부분)

경고: 로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다. 로그인하거나 계정을 생성하면 편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.

= 계산 복잡도 (Computational Complexity) =

알고리듬의 수행에 필요한 시간과 메모리 사용량이 입력의 크기에 따라 변화하는 정도를 정량적으로 나타낸다. 전자를 시간 복잡도(time complexity) 후자를 공간 복잡도(space complexity)라고 한다. 계산 복잡도는 특정 문제에 대해 정의되는 것이 아닌 문제를 해결하는 알고리듬에 대하여 정의되며 같은 문제에 대해서도 알고리듬에 따라 다른 시간 복잡도와 공간 복잡도를 가질 수 있다.

* 점근 표기법 (Asymptotic Notation)
알고리듬의 소요 시간이나 메모리 사용이 문제의 크기 $$n$$에 관한 함수 $$f(n)$$ 으로 정의 될때, $$n$$이 커짐에 함수의 증가를 다른 함수와의 점근적 대소관계로 표현하는 방법이다.<ref name=Cormen>T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, ''Introduction to algorithms'' (MIT press, 2009).</ref> 큰(big) $$O$$ 표기법, 작은(small) $$o$$ 표기법, 큰(big) $$\Omega$$ 표기법, 작은(small) $$\omega$$ 표기법과 큰(big) $$\Theta$$ 표기법 등이 존재하며 일반적으로 복잡도의 상한을 정의하는 큰(big) $$O$$ 표기법이 가장 범용적으로 사용된다.

* 큰 (Big) $$O$$ 표기법
복잡도가 입력의 크기 $$n$$에 대해 $$f(n)$$이라는 관계를 가질 때, $$f(n) \in O(g(n))$$이라는 것은 다음을 의미한다.

\[\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)} < \infty\]

즉, 충분히 큰 $$n$$에 대해, $$g(n)$$의 상수배가 $$f(n)$$의 상한이라는 것을 의미한다.

* 작은 (Small) $$o$$ 표기법
큰 $$O$$와 유사하지만 $$f(n)$$ 이 $$g(n)$$ 보다 점근적으로 엄격하게 작다(strictly less)는 것을 의미한다.

\[f(n)  \in o(g(n)) \Leftrightarrow \lim_{n \rightarrow \infty}\frac{f(n)}{g(n)}= 0\]

* 큰 (Big) $$\Omega$$ 표기법
큰 $$O$$와 반대로 $$f(n)$$이 $$g(n)$$ 보다 점근적으로 크다는 것을 의미한다.

\[f(n)  \in \Omega(g(n)) \Leftrightarrow \lim_{n \rightarrow \infty}\left| \frac{f(n)}{g(n)} \right| > 0\]

* 작은 (Small) $$\omega$$ 표기법
작은 $$o$$ 와 마찬가지로 $$f(n)$$이 $$g(n)$$ 보다 엄격하게 크다(strictly large)는 것을 의미한다.

\[f(n)  \in \omega(g(n)) \Leftrightarrow \lim_{n \rightarrow \infty}\frac{f(n)}{g(n)}= \infty\]

* 큰 (Big) $$\Theta$$ 표기법
$$f(n)$$이 $$O(g(n))$$이면서 $$\Omega(g(n))$$임을 의미한다. 즉 충분히 큰 $$n$$에 대하여, $$g(n)$$의 두 상수배가 $$f(n)$$의 상한과 하한이 되므로, $$f(n)$$과 $$g(n)$$이 점근적으로 같다는 것을 의미한다.

\[f(n) \in \Theta(g(n)) \Leftrightarrow f(n) \in O(g(n)), f(n) \in \Omega(g(n))\]

일반적으로 기호의 남용임에도 불구하고,

\[f(n)  \in O(g(n))\]

인 경우,

\[f(n)= O(g(n))\]

이라고 표기한다. 예를 들어 $$f(n)= an^{2} + bn + c $$일때, $$f(n)= O(n^{2})$$이라 할 수 있는데, 왜냐하면 $$\lim\limits_{n \rightarrow \infty}\frac{f(n)}{n^{2}}= a < \infty$$이기 때문이다.

어떤 알고리듬의 시간 복잡도 $$f(n)$$이 $$O(n^{a})$$ 인 경우 해당 알고리듬은 다룰 수 있는(tractable) 알고리듬으로 분류되고 $$f(n)$$이 $$O(a^{n})$$인 경우에는 다루기 힘든(intractable) 알고리듬으로 분류된다. 다루기 힘든 알고리듬의 경우 $$n$$이 커짐에 따라 소요 시간이 지수적으로 증가하므로 실질적인 의미에서 풀 수 없다고 볼 수 있다.

* P 문제
다항시간의 시간 복잡도를 가진 알고리듬이 발견된 문제들이다. 고전 컴퓨터로 효율적으로 풀 수 있다. 조금 더 정확히 말하면, 다항시간 내에 결정론적으로(deterministically) 풀 수 있는 결정문제(decision problem)이다. 결정문제란 예, 아니오의 형태로 답하는 문제인데, 많은 문제들이 다항시간 안에 결정문제로 변환될 수 있기 때문에 문제 분석에 활용된다.

* NP 문제
답이 주어졌을 때 다항시간의 복잡도로 답을 검증할 수 있는 문제이다. 또는 다항시간 내에 비결정론적(non-deterministically)으로 풀 수 있는 결정문제(non-deterministic polynomial time class)이다. 비결정론적이라는 것은 같은 문제에 대해 알고리듬을 실행할 때 얻는 결과가 달라질 수 있음을 의미한다. 즉, NP 문제는 항상은 아니지만 다항시간 내에 풀 때도 있다는 것이다. P 문제는 다항시간 안에 결정론적으로 해를 구할 수 있으므로 자명하게 NP 문제에 포함되며 P문제에 속하는 것이 증명이 되지 않은 경우 암호화 등에 사용된다. [[양자 컴퓨터]]는 소인수분해나 이산 로그(discrete logarithm)와 같은 NP 문제를 다항시간내에 풀 수 있기 때문에 기존에 사용되는 암호화 알고리듬을 무력화할 가능성이 크다. 양자 알고리듬의 고전 컴퓨터 알고리듬에 대한 우위는 동일한 알고리듬이 양자 컴퓨터에서 더 나은 수행시간으로 실행가능한지로부터 말할 수 있는 것이 아니라, 동일한 문제가 양자 컴퓨터에서 더 나은 시간 복잡도를 가질 수 있다는 사실로부터 나온다고 할 수 있다.

요약:

한국양자정보학회 위키에서의 모든 기여는 다른 기여자가 편집, 수정, 삭제할 수 있다는 점을 유의해 주세요. 만약 여기에 동의하지 않는다면, 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다(자세한 사항은 한국양자정보학회 위키:저작권 문서를 보세요). 저작권이 있는 내용을 허가 없이 저장하지 마세요!

취소 편집 도움말 (새 창에서 열림)

원본 주소 "https://wiki.qisk.or.kr/양자_알고리듬_(Quantum_Algorithm)"

양자 알고리듬 (Quantum Algorithm) 편집하기 (부분)

둘러보기 메뉴

검색