프로그램 작성 시에 계산시간을 줄이고 메모리를 효과적으로 사용하기 위해 고민해야한다.
첫 번째 이유는 프로그램의 규모가 이전에 비해서는 엄청나게 커지고 있기 때문이다. 처리해야 할 자료의 양이 많아질 수록 알고리즘의 효율성이 더욱 중요해진다.
두 번째 이유는 사용자들이 여전히 빠른 프로그램을 선호하기 때문이다.
효율적인 알고리즘이란 전체 실행 시간이 짧으면서 메모리와 같은 컴퓨터의 자원들을 적게 사용하는 알고리즘이다. 일반저으로 실행 시간이 메모리 공간보다 더 중요하게 생각되기 때문에 알고리즘의 실행 시간을 효율적인 알고리즘의 기준으로 삼는다.
공간복잡도에 대해서는 많이 기재하지 않겠다. 이유는 과학기술의 발달로 인해 일반적으로 메모리의 용량이 상당히 증가했기 때문이다.
물론 IOT(사물인터넷)이나 한정적인 메모리를 사용하는 경우가 있으나 알고리즘에 있어서는 중요도가 공간복잡도에 비해 시간복잡도가 훨씬 중요하기 때문이다. 물론 공간복잡도가 중요하지 않다는 것은 아니다. 기업입장이나 개인입장이나 똑같이 사용되는 메모리를 줄이면 경제적으로 많이 이득이 되기 때문이다. 나중에 기회가되면 공간복잡도에 대해 기재하겠다.
■ 알고리즘의 복잡도 분석 방법
알고리즘을 직접 구현하지 않고서도 대략적인 효율성을 분석할 수 있는데, 이것을 알고리즘 복잡도 분석(complexity analysis)이라 한다. 이 방법은 구현하지 않고도 모든 입력을 고려하는 방법으로 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.
알고이즘 분석에서는 먼저 "좋다"는 의미를 분명히 하여야 한다. 좋은 알고리즘은 실행 시간이 빠르고 처리를 위해 필요한 기억 공간이 적은 알고리즘이다. 알고리즘의 실행 시간 분석을 시간복잡도(time complexity)라고 하고 알고리즘이 사용하는 기억 공간 분석을 (space complexity)라고 한다. 우리가 알고리즘의 복잡도를 이야기할 때 대개는 시간 복잡도를 말한다.
■ 시간 복잡도 함수
시간복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지를 숫자로 표시한다. 연산에는 산술 연산, 대입 연산, 비교 연산, 이동 연산, 등이 모두 포함되는데, 복잡도 분석에 이들 연산의 실행횟수를 사용한다.
어떤 알고리즘을 실행하는데 필요한 연산의 수는 보통 주어지는 입력의 개수 n의 영향을 받는다. 이와 같이 연산의 수를 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T(n)이라고 표기한다.
n이 커질 수록 알고리즘산의 연산 양의 차이가 커진다. 따라서 가장 효율적인 알고리즘이 무엇인지 판단할 수 있다.
■ 빅오 표기법
일반적으로 시간 복잡도 함수 T(n)은 입력의 개수 n에 대한 상당히 복잡한 수식으로 나타날 수 있다. 그러나 자료의 개수가 많아질수록,
즉 n이 커질수록 T(n)에서 차수가 가장 큰 항의 영향이 절대적이 되고 다른 항들은 무시될 수 있을 정도로 작아진다. → 중요
T(n)의 최고차항의 영향이 n의 증가에 다라 점점 커져 다항식(ploynomial)에서 최고차항의 비율이 100%로 수렴한다. 이것은 시간 복잡도 분석에서는 함수의 전체 항이 아니라 최고 차항만을 고려하면 될 것임을 알려준다.
결국 시간 복잡도 함수에서 중요한 것은 연산이 몇 번 필요한가가 아니라 무엇에 비례하는 수의 연산이 필요한가이다.
이와 같이 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다.
→ 알고리즘이 n에 비례하는 실행 시간을 가진다고 말하는 대신에 알고리즘 A의 시간복잡도가 O(n)이라고 한다.
정의
두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0 에 대해 |f(n)| ≤ c|g(n)|을 만족하는 사수 c와 n0 가 존재하면 f(n) = O(g(n))이다.
■ 빅오 표기법 이외의 표기법
빅오 표기법 이외의 표기법에는 빅 오메가와 빅 세타 표기법이있다.
빅 오메가는 어떤 함수의 하한을 표시하는 방법이다.
정의
– 모든 n≥n0에 대하여 |f(n)| ≥ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=Ω(g(n))이다.
빅 세타는 동일한 함수로 상한과 하한을 만들 수 있는 경우, 즉 –f(n)=O(g(n))이면서 f(n)= Ω(g(n))인 경우를 f(n)= θ(n)이라고 한다.
정의
– 모든 n≥n0에 대하여 c1|g(n)| ≤ |f(n)| ≤ c2|g(n)|을 만족하는 3개의 상수 c1, c2와 n0가 존재하면 f(n)=θ(g(n))이다.
■ 최선, 평균, 최악의 경우
· 최선의 경우(best case)는 실행 시간이 가장 적은 경우를 말하는데, 알고리즘 분석에서는 큰 의미가 없다. → 빅 오메가 표기법 사용
· 평균적인 경우(average case)는 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 실행 시간을 의미하는데 산출하기 어렵다. → 빅 세타 표기법 사용
· 최악의 경우(worst case)는 자료 집합 중에서 알고리즘의 실행 시간이 가장 오래 걸리는 경우를 말하는데, 가장 중요하게 사용된다. → 빅 오 표기법 사용
알고리즘의 시간 복잡도로 최악의 경우의 실행 시간이 많이 쓰인다. 이것은 최대한 불리한 입력의 데이터를 사용하는 것으로쳥균적인 실행 시간보다 더 중요한 의미를 가지는 경우가 많다.
잘못된 정보나 오류, 오타, 독자 입장에서의 수정사항 및 피드백 환영합니다.
E-mail : jhmh0226@gmail.com
'Study Fundamental > Algorithm' 카테고리의 다른 글
| 분할 정복 알고리즘 (Divide-and-conquer) (0) | 2021.01.18 |
|---|---|
| 알고리즘 (0) | 2021.01.04 |