[자료구조] 1. 알고리즘 성능함수

알고리즘이란 컴퓨터로 문제를 해결하는 유한하고 단계적인 해법이다. 알고리즘의 조건으로는 다음 3개가 있다.

• 유한성 (finite)
• 명확한 답 (correct answer)
• input ≥ 0, output ≥ 1

이러한 알고리즘들은 문제를 해결한 것에 그치지 않고 성능 분석이 필요하다.

 

알고리즘의 성능

컴퓨터에서 성능은 복잡도로 표현할 수 있고, 복잡도는 시간과 공간으로 나눌 수 있다. 시간 복잡도는 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 메모리 효율성을 의미한다. 이러한 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈같은 연산 횟수로 정해지며 성능함수로 나타낼 수 있다.

 

ex)

성능 함수의 특징으로는 상수는 무시하며 차수는 중시한다.

위의 예시는 빅오(big-O) 표기법이며 추가로 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.

 

성능 함수의 수학적 정의

• 𝑓(𝑥)=𝑜(𝑔(𝑥))f(x)=o(g(x)): 임의의 𝑐>0c>0에 대해 𝑀M이 존재하여 𝑥>𝑀⇒∣𝑓(𝑥)∣≤𝑐𝑔(𝑥)x>M⇒∣f(x)∣≤cg(x)
• 𝑓(𝑥)=Ω(𝑔(𝑥))f(x)=Ω(g(x)): 𝑀,𝑐>0M,c>0이 존재하여 𝑥>𝑀⇒∣𝑓(𝑥)∣>𝑐𝑔(𝑥)x>M⇒∣f(x)∣>cg(x)
• 𝑓(𝑥)=Θ(𝑔(𝑥))f(x)=Θ(g(x)): 𝑓(𝑥)>0f(x)>0 중에서 𝑓(𝑥)=𝑂(𝑔(𝑥))f(x)=O(g(x))이며 𝑓(𝑥)=Ω(𝑔(𝑥))f(x)=Ω(g(x))

간단히 말해 빅오의 경우 최악의 상황을 가정하고 빅오메가의 경우 최선의 상황을 가정한다. 빅세타는 빅오와 빅오메가를 동시에 성립할 때, 즉 최악과 최선 중 하나를 선택한다. n^2 + n 식 같은 경우에서 빅오는 n^2의 시간 복잡도를, 빅오메가는 n의 시간 복잡도를 말한다.

(*) 성능함수의 성질

• 반사적
• 대칭적
• 투이적

알고리즘의 성능을 말할때 대부분 빅오 표기법을 사용한다.

 

자료구조들의 성능

자료구조에서 가장 중요한 요소는 삽입, 삭제, 검색이며 위 이미지는 자료 구조들의 성능 표이다. C++로 직접 구현해보며 삽입, 삭제, 검색에 있어서 성능 효율이 왜 이렇게 나오는지 알아보자.