흔히 알고리즘에서 쓰이는 복잡도(Complexity)란 그 알고리즘이 얼마나 효율적인지를 나타내는 지표의 의미
특정 알고리즘이 어떠한 입력에 대하여 연산을 수행할 때얼마만큼의 시간이 걸리는지(시간 복잡도,Time Complexity)와 얼마만큼의 메모리를 사용하는지(공간 복잡도, Space Complextiy) → 이 2가지 관점에 대한 효율성을 측정하기 위한 개념
즉, 알고리즘의 성능을 판단하는 척도
시간 복잡도(Time Complextiy)
알고리즘이 얼마나 시간적으로 효율적인지, 즉 얼마나 짧은 시간 안에 연산을 수행할 수 있는지를 나타내는 지표로 의미적으로는 시간적인 개념이지만 실제로 코드에서 측정되는 대상은 '실행되는 연산의 횟수'
동일한 알고리즘이어도 실행되는 컴퓨터 성능이 좋으면 시간이 더 적게 걸리고 성능이 안 좋으면 더 오래 걸릴테니, 동일한 하드웨어 환경에서 동일한 코드를 실행하였을 때실행되는 연산의 수를 기준
실행되는 연산의 횟수를 따지는 복잡도인데, 단순히 특정한 입력에 대하여 실행되는 연산의 횟수만 보는게 아니라 입력의 크기가 증가함에 따라실행되는 연산의 횟수(= 실행되는데 걸리는 시간)가 얼마나 증가하는지를 나타내는 것
동일한 환경에서 동일한 코드를 실행하였을 때 입력 n의 크기가 증가함에 따라 실행되는데 걸리는 시간이 증가하는 그래프가 어떤 모양인지를 나타내는 것 → 즉 입력과 (문제를 해결하는데 걸리는)시간의 함수 관계를 나타내는 개념
시간복잡도 측면에서 효율적인 알고리즘이라는 것은 이런 함수의 그래프의 기울기가 작은 것
이는 곧 입력의 크기가 증가함에 따른 시간의 증가 비율을 최소화했다는 의미
n의 크기의 증가에 따른 시간의 증가 그래프가 어떤 함수의 모양인지를 본다는 것은 n이 무한대로 갈 때 어떤 함수의 모양에 근접해지는지를 본다는 의미 → 점근적 분석(Asymptotic Analysis)
입력과 실행 시간의 함수를 점근적 분석을 통해 어떠한 일반적인 함수로 표현하는 표기법을 '점근적 표기법' → 이 표기법이 곧 시간복잡도의 표기법
시간복잡도의 표기법은 3가지 표기법이 존재
Big-O (빅-오) : 최악의 경우를 고려 (상한 점근) Big-Ω (빅-오메가) : 최선의 경우를 고려 (하한 점근) Big-θ (빅-세타) : 평균적인 경우를 고려 (상한과 하한의 평균)
반복문을 써서 0번 인덱스부터 순서대로 배열을 순회하여 찾는 값과 동일한 값을 가진 요소를 찾는 상황이라고 가정
동일한 알고리즘을 사용해도 찾는 요소가 배열의 앞쪽에 있으면 요소 몇 개만 순회하면 되니 시간이 적게 걸리고, 찾는 요소가 배열의 끝부분에 있으면 거의 N개의 요소를 순회해야 하므로 시간이 소요
Big-O(빅오) 표기법은 최악의 경우로 찾는 요소가 N번 인덱스에 있는 상황에서의 코드의 연산 횟수를 따지는 표기법
요소를 순회하는 연산을 N번 해야하는 최악의 경우를 상정하는 것이고, 이는 즉 "이 코드의 연산 횟수는 아무리 많아도 N 이하다" 라는 상한 점근의 의미
Big-Ω(빅오메가) 표기법은 최선의 경우를 상정하여 나타내는 표기법으로, 위의 경우에서는 찾는 요소가 0번 인덱스에 있는 상황에서의 코드의 연산 횟수
따라서 요소를 순회하는 연산을 1번 하는 최상의 경우를 의미하고 이는 "이 코드의 연산 횟수는 아무리 적어도 1 이상이다" 라는 하한 점근의 의미
Big-θ(빅세타) 표기법은 그냥 최악의 경우와 최상의 경우의 평균치를 나타내는 표기법으로, 위의 경우에서는 찾는 요소가 중간쯤(N/2번 인덱스)에 있는 상황에서의 코드의 연산 횟수
보통 코드의 시간복잡도를 나타낼 때에는 최악의 경우를 상정한 Big-O 표기법을 사용
코드의 실행이 금방 끝나는 운좋은 경우의 값을 내세우며 효율성을 이야기하는 것 보다는 최악의 상황일 때의 값으로 따져 아무리 오래걸려도 이정도의 시간을 넘지는 않는다는 것을 보여주는게 코드의 일반적인 효율성을 보여주기에 타당함
따라서, 어떠한 알고리즘의 시간적인 효율을 판단할 때에는 시간복잡도를 보통 Big-O 표기법으로 나타내어 최악의 경우에 걸리는 시간을 기준으로 알고리즘의 성능을 표시
시간 복잡도 측정
Big-O 표기법을 기준으로 시간복잡도를 계산하는 방법
int sum = 0;
for (int i = 1; i <= N; i++) {
sum += i;
}
N이 input 값이라고 했을 때 이 코드는 1부터 입력받은 값 N 까지의 총 합을 구하는 코드
이 코드에서 수행되는 연산의 총 횟수를 구해보면 int sum = 0 과 for문의 int i = 1은 코드의 최초 시행 시 한 번씩만 실행 → 실행 횟수 2
for문의 i++ 와 sum += i 는 for문이 실행될 때 마다 실행되는 연산이므로 for문이 N번 실행되는 상황에서는 각각 N번씩 실행 → 실행 횟수 2N (편의상 보통 for문에서는 for문의 int i = 1 이나 i++ 같은 내용까지는 따지지 않고 for문 안의 로직이 몇번 실행되는지만 따졌을 때 sum += i 라는 연산이 N번 실행되는 거니까 실행 횟수는 N)
따라서, 위 코드에서 실행되는 연산의 총 횟수는 2N+2
연산의 총 횟수를 구했을 때최고차 항을 제외한 나머지 항을 없앤 뒤 최고차 항의 계수를 없애면Big-O 표기법의 시간복잡도
시간복잡도는 N의 크기가 엄청나게 큰 상태일 때'가장 영향을 많이 끼치는 항 하나'로 표시하기 때문
2N+2에서 N이 증가함에 따라 2N은 기울기가 2인 선형 그래프로 한없이 값이 커지지만2는 그냥 상수이므로 N이 1이든 10이든 10억이든 항상 값은 2 → 따라서 N이 무한대로 갔을 경우 2는 2N에 비해 비교할 수 없을 정도로 작은 값이기 때문에 무시 가능
그래서 상수인 2는 제외하고 최고차항인 2N이 남고, 남은 최고차항의 계수 또한 무시가 가능한 값으로 취급
2N과 N은 분명 N이 커질수록 차이가 커지긴 하지만 우리가 코드에서 시간복잡도를 따져서 보는 포인트는N이 증가함에 따라 시간이 어떤 비율로 증가하는지이기 때문
값이 선형으로 증가하는지, 비선형으로 증가하는지, 상수처럼 변함이 없는지 등 함수 그래프의 모양이 중요하기 때문에 N의 차수가 중요한 것이고 계수는 중요한 파라미터가 아님
그래서 위의 예시 또한 2N이나 N이나 N이 증가함에 따라 값이 '선형적'으로 증가한다는 점은 동일하기 때문에 계수를 생략하여 N이라는 값을 도출해 내는 것
따라서 위 코드는 Big-O 표기법으로 O(N) 이라는 시간 복잡도를 가지는 알고리즘
시간 복잡도 측정2
// 3번 할당
int a = 0;
int b = 0;
int c = 0;
// n*3n번 할당
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
a = i*j;
b = i*j;
c = i*j;
}
}
// 2n번 할당
for (int k = 0; k < N; k++) {
a = b * k + 45;
b = c * k;
}
// 1번 할당
int d = 10;
4개의 변수 할당문은 N의 값에 상관없이 1번씩 선언되므로 총 4 (a, b, c, d)
2중 for문은 내부의 for문이 한 사이클당 3번의 연산을 하므로 N번의 사이클이면 3N번의 연산 ( a = i * j, b = i * j, c = i * j) → 3N번의 연산 자체가 외부 for문에 의해 N번 실행되므로 총 실행 횟수는 3N^2
1중 for문은 한 사이클당 2번의 연산을 하므로 N번의 사이클이면 총 실행횟수는 2N
따라서 이 코드는 총 3N^2 + 2N + 4 의 실행 횟수를 가지는 로직
이를 앞서 설명한 규칙으로 최고차항이 아닌 항들을 제거하고 최고차항의 계수를 제거하여 O(N^2) 이라는 시간복잡도를 가짐
이런식으로 실행 횟수를 계산하여 만든 함수가 어떤 형태의 함수에 점근적으로 근접하는지를 따져서 나타내는게 시간복잡도의 Big-O 표기법이고, 알고리즘의 시간복잡도를 나타낼 때표준으로 사용하는 지표
시간 복잡도의 종류
O(1)
입력값이 증가하더라도 걸리는 시간이 증가하지 않는 상수 연산의 복잡도
'일정한 복잡도(constant complexity)' 라고도 부르며 입력값의 크기에 상관없이 가장 빠른, 가장 이상적인 시간 복잡도
O(log n)
그래프가 로그함수의 모양으로 나타나며 '로그 복잡도(logaritmic complextiy)' 라고도 부름
입력값이 증가하면 걸리는 시간이 증가하다가 어느 정도 이상부터는 거의 증가하지 않기 때문에 N -> ∞ 인 스케일에서는 O(1) 그래프의 모습과 별로 차이가 없는O(1) 다음으로 빠른 복잡도
O(n)
선형적으로 증가하기 때문에 '선형 복잡도(linear complexity)' 라고 부름
입력값이 증가함에 따라 걸리는 시간도 같은 비율로 증가하는 복잡도
O(n^2)
그래프가 2차 함수의 모양으로 나타나며 '2차 복잡도(quadratic complexity)' 라고 부름
주로 중첩 반복문인 경우 나타나는 유형의 복잡도
O(2^n)
그래프가 지수 함수의 모양으로 나타나며 '기하급수적 복잡도(exponential complexity)' 라고 부름
2차 함수 보다도 더 기하급수적으로 올라가는 복잡도로 Big-O 표기법중 거의 가장 느린 시간 복잡도 → 가장 느린 것은 O(n!) 팩토리얼
Big-O 시간 복잡도
시간 복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 되는 지표
시간 복잡도의 차수를 높이는 주된 요인이 보통 반복문의 중첩인데 같은 로직이어도 반복문을 최대한 중첩시키지 않는 방향으로 설계하여 O(N^2) 보다는 O(N)을, O(N) 보다는 O(log n), O(log n)보다는 O(1)을 지향하는게 효율적인 알고리즘을 짜는 가장 중요한 마스터키가 될 것
공간 복잡도(Space Complextiy)
공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
알고리즘이 얼마나 많은 메모리 공간을 차지하는지에 초점을 맞춰 효율성을 분석하는 지표
int[] a = new int[1000];
위와 같은 배열을 선언했다고 치면 배열의 요소는 int형이므로 4byte이고, 이러한 요소가 1000개 있는 것이므로 차지하는 메모리 공간의 총량은 4000byte → 이러한 공간을 의미
보통 공간 복잡도는 시간 복잡도와 반비례하는 경향이 있음
시간적으로 효율적인 로직을 짜기 위해서는 이런저런 변수를 사용하는 등 메모리 공간을 더 투자하는 경향이 많기 때문에 시간 효율성과 공간 효율성을 동시에 챙기기란 현실적으로 굉장히 어렵다고 함
하지만 요즘은 하드웨어의 발달로 인해 메모리 공간이 굉장히 넉넉해졌기 때문에 공간 복잡도의 중요도가 많이 낮아졌고, 시간 복잡도를 고려하지 않았을 때의 프로그램 실행 시비효율성이 훨씬 크기때문에 요즘은 공간 복잡도보다는 시간 복잡도를 더 우선하여 효율성을 고려
