[ 알고리즘 ] 시간 복잡도와 공간 복잡도에 대하여

시간 복잡도 ( Time complexity )

프로그램이 실행될 때, 입력값과 연산 수행 시간의 상관 관계를 나타내는 척도.
보통 점진적 표현법을 사용함

재밌는 예시를 하나 들자면, 친구가 무한 아파트로 이사를 가서 집들이를 하려고 한다.
친구가 번지, 동, 호수를 알려줬다면 그냥 그곳으로 찾아가면 된다. 시간 복잡도는 O(1) 이다
만약 친구가 번지, 동 을 알려줬는데 호수를 까먹었다면 b 동의 101 호 부터 찾아보면 된다.
이때 시간 복잡도는 O(n) 이다.
친구가 번지만 알려줬다면, 1동 101 호부터 하나하나 찾아본다면 동 * 호수 만큼의 시간이 걸릴 것이다.
이 때 시간 복잡도는 O(n²) 이다.
친구가 아무것도 알려주지 않았다면, 번지, 동, 호수를 다 찾아봐야한다 이 때 번지* 동 * 호수만큼의 시간이 걸리니 시간 복잡도는 O(n³) 이다. (알려달라고 전화하는게 제일 빠를거같다..)

Big - O 표기법이란 점근적 표기법 중 하나로, 최악의 수행 시간을 고려해서 표기하는 방법이다.

다른 방법으로는 최적의 시간을 나타내는 빅 오메가 (Big-Ω) 와 평균 시간을 나타내는 빅 세타(Big-θ)가 있다.

이렇게 표기하는 이유는 n 의 값이 커지면 커질수록 상수 값이나, 낮은 차항의 값이 알고리즘에 미치는 영향이 최고 차항에 비해 적기 때문에 복잡한 뒤의 식은 생략하는 방식을 사용한다.

시간 복잡도를 줄이는 방법은, 쓸모 없는 연산을 줄이거나 반복문을 줄이는 등 연산의 횟수를 어떻게든 줄이면 시간 복잡도가 줄어든다. 보통 동적 프로그래밍의 메모이제이션을 통해 지수 시간이였던 피보나치 수열을 선형 시간으로 줄일 수 있다.

비효율적인 알고리즘을 효율적인 알고리즘으로 변경
- 외판원 문제는 브루트 포스를 사용해서 풀면 팩토리얼 시간 O(n!) 이 소모되는 알고리즘이다.
  이는 n 이 12를 넘어가면 보통 1초에 1억회 연산이 이루어진다는 가정에 4.8억으로 약 5초가 소요된다.
- 하지만 이를 동적 계획법을 사용해서 푼다면, 지수 시간 ( 2^n ) 에 푸는 문제가 된다.
  약 2^12 는 4096 으로 약 십만배 가까이 빠른 알고리즘이다.
반복문 숫자 줄이기.
적절한 자료구조 사용하기
- 만약 검색보다 삽입과 삭제가 많다면, 삽입과 삭제가 빠른 자료 구조인 Stack 이나 Linked List 를 사용하는 것이 더 좋을것이다.

프로그램이 수행되는데 사용되는 자원 공간의 양을 의미

프로그램이 실행되는데 사용되는 메모리 등의 자원 공간의 양을 의미한다.

총 요구되는 공간의 양은 고정 공간 요구와 가변 공간 요구의 합으로 S(P) + c + Sp(n) 으로 표기한다.

고정 공간이란, 입력 출력 횟수와 상관없는 공간의 요구를 의미하며 가변 공간이란 변수 등 동적 할당이 들어가는 공간을 의미한다.

일반적으로 공간 복잡도는 시간 복잡도와 상반하는 개념이기에 보통의 경우에는 공간 복잡도를 희생해서 시간 복잡도를 챙기는 경우가 많다. 하지만, 극한으로 시간 복잡도를 챙긴 Galactic Algorithm 등의 알고리즘은 사용 할 수 없을것이다.

실제 상황에서는 임베디드 나 게임, 펌웨어 등 한정된 메모리 자원을 사용하는 경우나, 빅 데이터 같은 엄청 큰 저장 공간을 다루는 경우에는 공간 복잡도도 유의미하게 다룬다.

공간 복잡도를 적게 사용하는 알고리즘을 사용
- 병합 정렬과 버블 정렬을 비교하면 시간 복잡도는 O( n log n ) vs O(n²) 로 병합 정렬이 빠름
- 하지만 공간 복잡도는 O(n) 과 O(1) 로 버블 정렬이 더 적은 자원을 소모함을 알 수 있음
- 이래서 여러가지 종류의 Sort 알고리즘이 존재한다.
분산 처리 시스템을 사용하여, 한번에 큰 데이터를 처리하지 않음으로 과부하를 줄이고 빠른 연산이 가능.

Reference