[CS 개념 정리] 시간/공간 복잡도, 완전탐색, 순열/조합/부분집합

시간/공간 복잡도

시간 복잡도 : 알고리즘의 수행시간 분석

공간 복잡도 : 알고리즘의 메모리 사용량 분석

 

1. 시간 복잡도

: 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간

 

시간 복잡도의 '빅-오 표기법'

: 알고리즘의 효율성을 표기해주는 표기법, 점근적 실행 시간을 표기할때 쓰이는 수학적 표기 방법이다.

여기서 점근적 실행 시간이란 간단하게 n이라는 입력값이 무한대로 커질떄의 실행 시간의 추이를 의미한다.

 

[시간 복잡도]

O(1) (Constant)

:입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.

O(log₂ n) (Logarithmic)

:입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.

O(n) (Linear)

:입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있습니다.

O(n log₂ n) (Linear-Logarithmic)

:데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적입니다.

O(n²) (quadratic)

:데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다.

O(2ⁿ) (Exponential)

:데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다. 

 

빅오 표기법 예제

1. O(1) : 스택의 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2ⁿ) : 피보나치 수열

 

2. 공간 복잡도

공간 복잡도(Space Complexity)란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법

 

• 시간과 공간은 반비례적 경향이 있음. 알고리즘은  "시간과 공간이 트레이드오프 관계이다" (트레이드 오프 : 하나가 증가하면 다른 하나는 감소한다.)
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
• 알고리즘은 시간 복잡도가 중심

 

빅오 표기는 복잡하 함수 f(n)이 있을 경우 이 함수의 실행 상한과 하한을 의미힌다.

즉, 가장 빨리 실행될때가 하한, 가장 늦게 실행될때가 상한을 뜻한다.

이 중 가장 늦게 실행될 때를 빅오(O), 가장 빨리 실행될 때를 빅오메가(Ω), 평균을 빅세타(θ) 로 지칭한다.

n이 작을때, 즉 n0 이하 일때의 값이 작은 경우는 무시하며! 빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중한다.

 

 

>> 결론, 빅오 표기법은 주어진(최선/평균/최악) 경우의 수행 시간의 상한을 나타낸다

 

 

---

완전탐색(Exhaustive search, Brute force)

: 모든 경우의 수를 시도하는 방법

> 구현이 간단, 해가 존재하면 항상 찾음

> 경우의 수에 따라 실행시간 비례, 입력 값의 범위가 작은 경우 유용

 

완전탐색의 종류

1) Brute Force 기법

Brute Force 기법은 반복 / 조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 말한다. 예를 들어, 4자리로 된 번호 자물쇠를 푼다고 할 때 최악의 경우 10000 * 1초 = 대략 166분 (컴퓨터의 연산 속도 : 대략 1초에 1억) 이 걸릴 수 있다.

2) 백트래킹 (Backtracking)

백트래킹 (Backtracking)은 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 알고리즘이다. 분할정복을 이용한 기법으로, 재귀함수를 이용하고 해를 찾아가는 도중 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.

 

3) 비트 마스크

: 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두가지 선택으로 구성되는 경우 유용하게 사용 

> 비트니까,, 예시로 포함 여부를 0,1로 구분해 배열에 저장 가능

 

4) 재귀함수

: 자신을 정의할 때 자기 자신을 재참조하는 방법

- 비트마스크와 마찬가지로 원소가 두 가지 선택지일 때 유용

- 포함이 되면 해당 원소 넣어 함수 호출, 포함되지 않으면 그 상태에서 함수 호출

- ex. 피보나치 수열

- 시간복잡도 O(N)

 

5) 순열

- 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)를 말함

- 순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함.

- 순열에 원소를 하나씩 채워가는 방식

- 시간복잡도 O(N!)

 

6) DFS/BFS

 

 

 

---

조합

: n개의 값 중에서 r 개의 숫자를 순서를 고려하지 않고 나열한 경우의 수
순열과는 순서를 고려하지 않는 다는 점이 다르다

?? [1,2] 와 [2,1] 이 있을 때 동일하게 여긴다는 의미

 

> 계산식으로는 nCr 이라고 표현

 

nCr
= nPr / r!
= n! / ((n-r)! * r!)

 

점화식이란 ?

어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것

 

조합의 점화식

조합의 점화식은 다음과 같다.

n-1Cr-1 + n-1Cr

1. n-1Cr-1 : 어떤 특정한 원소를 포함시키고 뽑았을 때
2. n-1Cr : 어떤 특정한 원소를 포함시키지 않고 뽑았을 때

조합 vs 순열

조합과 순열은 상당히 유사한데 차이점이라고 하면

조합은 순서와 상관없이 나열 하는 경우의 수
순열은 순서를 고려해 나열 하는 경우의 수 이다

 

---

부분집합

부분집합이란 주어진 집합에 포함되어 있는 집합

 

파이썬에서 부분집합 구하기