개쿠

알고리즘이란 ?

문제를 해결하는 단계적 절차 또는 방법이다.

알고리즘의 특성 4가지

정확성 : 알고리즘은 주어진 입력에 대해 결과를 줘야 한다.

수행성 : 알고리즘은 컴퓨터에서 수행 가능해야 한다

유한성 : 알고리즘은 일정 시간 내에 종료되어야 한다

효율성 : 알고리즘은 효율적일수록 가치가 높아진다

알고리즘 표현 방법

프로그래밍 언어(JAVA, C 등) 혹은 의사 코드(pseudo code)로 표현한다.

알고리즘 효율성이란 ?

알고리즘의 효율성은 알고리즘의 수행 시간 혹은 수행하는 동안 사용되는 메모리 공간의 크기로 나타낸다.

                                  시간복잡도 (time complexity)                      공간복잡도 (space complexity)

일반적으로 알고리즘을 비교할 때 시간 복잡도가 주로 사용한다.

복잡도의 점근적 표기

점근적 표기(Asymptotic Notation) : 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법

O - (Big-Oh) 표기 : 복잡도의 점근적 상한을 표시

Ω - (Big-Omega) 표기 : 복잡도의 점근적 하한을 표시

θ - (Theta) 표기 : 복잡도의 하한과 상한을 표시

                                 O-(Big-Oh) 표기와 Ω-(Big-Omega) 표기가 같은 경우에 사용한다.

성능 비교

O(1) < O(log2N) < O(n) < O(Nlog2N) < O(n^2) < O(n^3) < O(2^n) < O(n!)