자료구조 / 알고리즘
자료구조(Data Structure)
- 데이터를 효율적으로 저장하고 관리하는 방식이나 구조를 의미
- 데이터를 저장하고 조작하는 방법을 정의하는 체계라고 보면됨
알고리즘(Algorithm)
- 특정 문제를 해결하기 위한 절차나 방법을 의미
- 데이터를 처리하고 조작하는 논리적인 과정이자, 일련의 명령어 집합이라고 보면됨
어떤 자료구조가 사용되었느냐에 따라 사용 가능한 알고리즘이 달라질 수 있기 때문에 자료구조와 알고리즘은 전혀 다른 개념이 아닌 깊은 연관성이 있음
시간 복잡도 / 공간 복잡도
- 개발자는 프로그램을 만드는 과정에서 소스 코드를 통해 다양한 데이터 다루고(자료구조), 그 데이터를 활용해 특정 목적을 이루기 위한 연산(알고리즘)을 구현
- 자료구조와 알고리즘을 고려하며 작성한 코드는 훨씬 더 좋은 코드가 될 가능성이 높음
시간 복잡도와 공간 복잡도는 소스 코드나 프로그램이 얼마나 효율적인지를 판단하는 척도
시간 복잡도
입력의 크기에 따른 프로그램 실행 시간의 관계
특정 데이터를 찾는 프로그램애서 데이터가 하나(N=1)인 프로그램보다
데이터가 100개(N=100)인 프로그램이 일반적으로 조금 더 오래걸림
이때 실행 시간은 연산의 횟수에 비례한다고 간주함
그래서 시간 복잡도는 입력의 크기에 따른 프로그램 실행 시간이라고 할 수도 있고, 입력의 크기에 따른 연산 횟수라고 할 수도 있음
1 + 1
1 + 1
1 + 1
1 + 1
1 + 1 // 1+1이 한 번의 연산을 의미한다면 다섯 번의 연산이 필요함for (int i = 0, i < n, i++) {
i++;
}
// 이 경우는 n번의 연산이 필요하고for (int i = 0, i < n * 2, i++) {
i++;
}
// 이 경우는 2n번의 연산이 필요하고for (int i = 0, i < n, i++) {
for (int i = 0, i < n, i++) {
i++;
}
}
// 이 경우는 n²번의 연산이 필요함다 합치면 (5 + 2n + n²)번이 됨
예제를 보면 반복문이 시간 복잡도에 많은 영향을 끼치는게 보이고,
실제로도 프로그램의 시간 복잡도에 가장 많은 영향을 끼치는 문법이 반복문임
N=1 보다 N=100 이 일반적으로 더 오랜 실행 시간이 소요됨
이라고 "일반적으로", "평균적으로"라는 사족을 붙인건 그렇지 않은 경우도 있음
최선의 경우, 운 좋게 단번에 원하는 데이터를 찾아낼 수도 있고,
최악의 경우, 데이터를 찾는 모든 연산을 끝내야만 원하는 데이터를 찾아낼 수도 있음
상황에 따라 동일한 입력에 대한 프로그램의 실행 시간이 들쑥날쑥하면 곤란함
그래서 시간 복잡도를 표현할 때에는 대중적으로 빅 오 표기법을 사용
📌 빅 오 표기법(Big-O)
함수의 점근적 상한을 표기하는 방법
> 점근적 상한: 최악의 경우 실행 시간이 증가하는 상한- 시간 복잡도를 표현하기 위해 빅 오 표기법을 사용한다면 "입력에 따른 실행 시간의 점금적 상한"을 의미
- 입력 크기 n이 무한대로 증가할 때, 실행 시간이 가질 수 있는 최대한의 증가율을 표현
- O(상한(n)) 형태로 표현
- 입력하는 n이 점점 증가해 무한대로 커진다 하더라도 실행 시간이 대략 이 이상(상한)은 커지지 않을 것이라는 의미
- O(n²)은 입력값 n이 증가하더라도 실행 시간의 증가율이 n²보다는 작다는 것을 표현
표기법 비교 / 수식
빅 오 표기법: 최악의 경우 성능을 보장하는 표기법(가장 대중적으로 사용)
모든 x >= Xo 에 대해 f(x) <= C * g(x) 를 만족하는 양의 상수 C 와 Xo 가 존재할 경우,
O(g(x)) = f(x)빅 세타 표기법: 평균적으로 실행 시간이 특정 범위에 속하는 경우
f(x) = O(g(x)) 와 f(x) = Omega(g(x)) 가 모두 성립할 경우,
Theta(g(x)) = f(x)빅 오메가 표기법: 최소한 이 정도 실행 시간은 보장됨을 의미
모든 x >= Xo 에 대해 f(x) >= c * g(x) 를 만족하는 양의 상수 c 와 Xo 가 존재할 경우,
Omega(g(x)) = f(x)시간 복잡도를 표현할 때는 빅 오 표기법이 가장 일반적이며, 코드의 성능 분석 기준이 됨
앞에 말한 "N=1 보다 N=100 이 일반적으로 더 오랜 실행 시간이 소요됨"을 보면,
n이 점점 커져서 무한대로 향하더라도 대략 n번 이상으로 연산하지는 않을 것
시간 복잡도를 빅 오 표기법으로 표현하면 O(n)이 됨
📌 대표적인 시간 복잡도 그래프
공간 복잡도
프로그램이 실행되었을 때 필요한 메모리 자원의 양을 의미
시간 복잡도가 입력에 따른 실행 시간의 척도라면, 공간 복잡도는 입력에 따른 메모리 사용량의 척도라 할 수 있음
- 모든 프로그램은 실행을 위해 메모리에 적재되어야 하며, 필요한 메모리 양에 따라 공간 복잡도가 결정됨
- 공간 복잡도는 빅오 표기법으로 표현되며, 입력 크기에 따른 메모리 사용량의 점근적 상한을 나타냄
- 하지만 알고리즘 성능 평가는 주로 시간 복잡도를 기준으로 하므로, 특별한 언급이 없으면 빅오 표기법은 시간 복잡도를 의미
자료구조 지도
다음 블로그에 올릴 내용들
추가 설명
시간복잡도
서랍에서 물건을 찾는데 걸리는 시간
O(1) - 상수 시간 복잡도
idx
O(n) - 선형 시간 복잡도
n단 서랍장에서 물건 찾기
for
O(log n) - 로그 시간 복잡도
n단 서랍장을 절반으로 나눠서 찾음
이진탐색
O(n²) - 제곱 시간 복잡도
n단 서랍장 한칸 안에 또 다른 n단 서랍장이 있음
중첩 for
공간복잡도
사용하는 서랍에 크기
O(1) - 상수 공간 복잡도
한칸짜리 서랍임 뭘 넣든 크기는 똑같음
num = 1
O(n) - 선형 공간 복잡도
물건 크기만큼 서랍 크기가 늘어남
return new int[n]
O(log n) - 로그 공간 복잡도
필요한 서랍을 절반씩 나누면서 사용함
O(n²) - 제곱 공간 복잡도
n단 서랍장 한칸 안에 또 다른 n단 서랍장이 있음
참고: 북스터디 - 이것이 취업을 위한 컴퓨터 과학이다 (Chapter 4-1)
