자료구조 - 알고리즘의 개념과 성능 그리고 자료구조와의 관계

알고리즘

알고리즘의 개념

컴퓨터가 문제를 해결하거나 특정 작업을 수행하기 위해 따라야 하는 추상화된 절차나 규칙의 집합 또는 명령어의 연속된 덩어리.

알고리즘의 조건

조건	설명
출력	알고리즘을 수행하고 나면 적어도 한 가지 결과를 생성해야 한다. 결과를 생성하지 않는다는 것은, 알고리즘 수행 이전과 이후에 차이가 없다는 것이고, 이것은 알고리즘을 수행할 필요가 없다는 것이므로 알고리즘의 존재 의미가 사라진다. 따라서 알고리즘은 수행하고 나면 적어도 한 가지 결과를 생성해야 한다.
유효성	알고리즘은 반드시 실행 가능해야 한다. 즉, 실행 가능한 명령어를 이용해 알고리즘이 만들어져야 한다.
입력	입력값은 반드시 형태가 정의될 수 있어야 하고, 그 수가 유한해야 한다.
명확성	명령들은 애매모호하지 않고 명확해야 함. 따라서 명령의 실행 주체가 누구더라도 같은 의미로 해석되고, 동일한 결과를 생성할 수 있어야 함.
유한성	반드시 종료가 명확하게 정의되어 있어야 함. (운영체제처럼 종료되지 않는 것을 목표로 하는 소프트웨어는 제외)

자료구조와 알고리즘의 관계

알고리즘은 컴퓨터가 수행할 명령어들의 모음이다. 그리고 자료구조는 이러한 명령어를 수행할 때 필요한 데이터를 저장하는 역할을 한다. 쉽게 말해, 자료구조는 알고리즘이 작동하기 위해 필요한 데이터를 조직하고 저장하는 창고와 같다고 할 수 있다.

따라서, 적절한 자료구조를 선택하면 알고리즘이 더 효율적으로 동작하여 원하는 성능에 가깝게 될 것이다. 반대로, 맞지 않는 자료구조를 사용한다면 알고리즘의 효율성이 떨어질 가능성이 높다.

이를 연결지어서 생각해보면, 자료구조의 효율성을 측정하는 방법 중 하나는 특정 알고리즘과 해당 자료구조를 함께 사용했을 때의 알고리즘 성능이나 효율성을 평가하는 것이다. 이를 위해 알고리즘의 성능 분석(예측) 과 측정에 대해 알아보자.

알고리즘의 성능

성능 분석과 성능 측정

알고리즘의 성능을 평가하기 위해서는 성능 분석과 성능 측정이라는 두 가지 방법으로 접근이 가능하다. 두 가지는 비슷해 보이지만 아래와 같은 차이가 있다.

구분	성능 분석	성능 측정
정의	이론적으로 자료구조나 알고리즘의 성능을 분석하는 과정	실제로 자료구조와 알고리즘을 실행해 성능을 측정하는 과정
평가 방법	보통 시간복잡도와 공간복잡도로 분석	실제 실행 기반으로, 실제 시간을 측정한다.
특징	직접 실행하지 않아도 되므로 경제적인 방법	실제 프로그래밍을 해야하며, 실행 환경에 따라 측정값이 다를 수 있다.
결과	일반적인 결과를 제공	특정 환경에 의존적인 결과를 제공
장점	일반적인 결과를 제공, 경제적임	현실적인 결과 제공, 특정 환경에 최적화 가능
단점	현실성과의 괴리, 복잡한 경우 분석 어려움	환경 의존성, 시간과 리소스 소모, 테스트 데이터 의존성

시간복잡도와 공간복잡도

시간복잡도와 공간복잡도는 알고리즘이나 자료구조의 성능을 평가하는 척도들을 의미한다.

구분	개념
시간복잡도	입력값의 크기(=개수)와 알고리즘의 연산 수행 시간 간의 상관관계를 분석하여 나타낸 것
공간복잡도	입력값의 크기(=개수)와 알고리즘이 실행시 사용하는 메모리의 양간의 상관관계를 분석하여 나타낸 것.

시간복잡도

시간복잡도란, 입력값의 크기(=개수)와 알고리즘의 연산 수행 시간 간의 상관관계를 분석하여 나타낸 것이다. 이는 알고리즘의 효율성을 평가하는 중요한 척도 중 하나이다. 보통 시간복잡도는 빅오 표기법을 사용한다.

시간복잡도	명칭	설명	예시
O(1)	상수 시간	입력 크기와 상관 없이 항상 일정한 시간이 걸리는 경우, 효율성이 매우 뛰어난 시간복잡도.	배열의 특정 인덱스에 접근 변수 값을 단순히 반환
O(logn)	로그 시간	입력 크기가 증가할수록 실행 시간이 매우 완만하게 증가하는 경우. 비교적 효율적인 시간복잡도.	이진 탐색
O(n)	선형 시간	입력 크기와 실행 시간이 선형적으로 비례해 증가하는 경우. 일반적으로 효율적. 대규모 데이터에서는 더 효율적인 알고리즘을 찾는 게 권장됨.	선형 탐색
O(nlogn)	선형 로그 시간	선형 시간과 로그 시간이 결합된 형태. 입력 데이터를 한 번 순회하면서, 각 단계에서 로그 시간의 작업을 수행하는 경우 발생. 비교 기반 정렬 알고리즘 중에 최선의 시간복잡도. 대규모 데이터 처리에 적합.	병합 정렬, 힙 정렬
O(n^2)	이차 시간	중첩 루프를 사용하는 알고리즘에서 주로 나타나는 시간복잡도 입력 데이터의 각 요소를 다른 모든 요소와 비교하거나 처리해야 하는 경우. 입력 크기가 커질수록 실행 시간이 매우 빠르게 증가. 데이터가 커질수록 비효율적	버블 정렬, 선택 정렬
O(2^n)	지수 시간	입력 크기가 증가할수록 실행 시간이 기하급수적으로 증가하는 시간복잡도 재귀적으로 모든 가능한 경우를 탐색하는 알고리즘에서 나타남 매우 비효율적이며, 현실적으로 큰 데이터 처리가 불가함	피보나치 수열의 비효율적 재귀 풀이
O(n!)	팩토리얼 시간	입력 데이터의 모든 순열을 생성하거나 조합을 시도해야하는 경우 입력 크기가 약간만 커져도 실행 시간이 급격히 증가함 실제로 사용할 수 없는 경우가 많다.	순열 생성 알고리즘

알고리즘의 실행시간 분석

알고리즘 실행 시간의 분석은, 알고리즘을 실행하는데 필요한 예측 실행시간을 추정하여 알고리즘의 성능을 분석하는 것을 의미한다. 실제로 알고리즘을 프로그램으로 구현하고 그에 따라 실제 작동 시간을 측정하는 것이 아니라, 알고리즘의 구조 등의 분석을 통해 실행 시간을 예측하는 것을 말한다.

공간복잡도

공간복잡도란, 입력값의 크기(=개수)와 알고리즘이 실행시 사용하는 메모리의 양간의 상관관계를 분석하여 나타낸 것이다. 이는 알고리짐의 효율성을 평가하는 또 다른 중요한 척도이다. 공간복잡도 또한 빅오 표기법으로 표현된다.

프로그램을 실행할 때에 사용되는 공간은 고정 공간, 가변 공간, 보조 공간 세 가지가 있다. 공간복잡도를 계산할 때에는 기본적으로 이 중 고정 공간과 가변 공간이 사용하는 공간을 대상으로 한다. (공간복잡도의 분석 대상 = 고정 공간 + 가변 공간)

공간복잡도

공간복잡도	명칭	설명	예시
O(1)	상수 공간	입력 크기와 상관없이 일정한 메모리만 사용하는 경우	배열A[n]의 첫 번째 요소를 찾는 함수
O(n)	선형 공간	입력 크기에 선형적으로 비례하여 메모리를 사용하는 경우	입력 데이터 복사
O(n^2)	이차 공간	입력 크기 n에 비례해 n^2의 공간이 필요한 경우	n*n 2차원 배열 생성 함수
		이외 생략

공간의 구분

공간	설명	예시
고정 공간	입력 크기와 관계없이 일정한 크기의 메모리 사용	상수, 고정크기 변수
가변 공간	입력 크기에 따라 달라지는 메모리 공간	배열, 리스트, 스택..
보조 공간	알고리즘 작업 수행동안 임시로 사용하는 추가 공간	임시 배열, 캐시 메모리..

알고리즘의 실행메모리 분석

알고리즘 실행메모리 분석이란, 알고리즘을 실행하는데 필요한 메모리 공간을 추정하여 알고리즘의 성능을 분석하는 방법을 의미한다.

시간복잡도와 공간복잡도의 관계

시간복잡도와 공간복잡도는 종종 상충 관계 (Trade-off) 를 보이곤 한다. 예를 들어, 캐시 메모리를 추가로 사용하면 알고리즘의 실행 시간을 단축시켜 시간복잡도를 줄일 수 있지만, 저장 공간을 더 많이 차지하여 공간복잡도가 늘어나게 된다.

Reference

자료구조 (강태원, 정광식 공저)