Complexity of Algorithms

1. Algorithms

알고리즘(Algorithm)은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위한 정해진 일련의 절차나 방법이다. 계산을 실행하기 위한 단계적 절차를 의미하며 프로그램 명령어의 집합을 의미하기도 한다.

 

2. Time Complexity

시간복잡도(Time Complexity)는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 즉, 문제를 해결하기 위한 알고리즘을 구성했다고 할 때, 입력값의 변화에 따라 연산에 진행되는 시간이 얼마나 걸리는가를 의미한다. 

 

시간복잡도는 기본적으로 최악 선택 복잡도(Worst-base Complexity)를 기준으로 계산하게 된다. 즉 if문에 대해서도 모든 값이 if문을 통과한다는 가정하에 시간복잡도를 계산하게 된다는 것이다. 

 

def maximum(values):
    answer = None                            # c1, 1 time,  c1
    for value in values:                     # c2, N times, c2*N
        if answer == None or answer < value: # c3, N times, c3*N
            answer = value                   # c4, N times, c4*N
    return answer                            # c5, 1 time,  c5

 

시간 복잡도는 연산의 종류, 입력값의 유무에 따라 종류가 다양하다. 코드 한줄 단위로 시간복잡도를 계산하고자 하면 정확한 시간 복잡도를 고려할 수 있지만, 알고리즘 내부의 코드가 길어지고 복잡해지게 되면 정확한 시간 복잡도를 계산하기란 어렵다. 

 

이때 시간 복잡도를 대략적으로 표현하기 위한 방법이 빅-오(Big-O) 표기법이다.

 

	종류	표기법
1	상수 시간 복잡도	$O(1)$
2	선형 시간 복잡도	$O(N)$
3	다항 시간 복잡도	$O(N^2)$
4	로그 시간 복잡도	$O(log(N))

 

상수 시간 복잡도(Constant Time Complexity)는 컴퓨터의 기본 연산들이 해당되며 저장소 위치에 값을 저장, 사칙 연산 등이 존재한다. 상수 시간 복잡도와 '비슷하게' 간주를 하는 복잡도인 분할 상환 분석(amortized analysis)이 존재한다. 분할 상환분석의 경우 최악 선택 복잡도로 계산을 진행하게 되면 O(N)의 시간 복잡도를 가지게 되지만, 연산 중의 극히 일부분만 N의 실행 단위를 가지고 있는 경우 '평균' 처럼 시간 복잡도를 간주한다는 개념이다. 

 

로그 시간 복잡도(Logarithmic Time Complexity)의 대표적인 알고리즘은 이진 검색 알고리즘(Binary Search Algorithms)이다. 이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘으로 정렬된 리스트의 장점을 사용해서 절반의 인덱스씩만 고려해서 값을 효율적으로 찾는 알고리즘이다. 

 

3. Space Complexity 

공간 복잡도(Space Complexity)는 프로그램을 실행시킨 후 완료하는데 필요한 자원 공간의 양으로 알고리즘에 해당되는 메모리의 크기(변수, 리스트)를 의미한다. 공간복잡도와 시간복잡도는 서로 반비례의 관계를 가지고 있는데, 시간 복잡도를 증가시키게 되면 공간 복잡도의 크기가 줄어들고, 공간 복잡도를 증가시키게 되면 시간 복잡도의 크기가 감소한다는 특징이 있다. 이를 적절히 균형을 맞추어 효율적인 메모리와 빠른 실행시간을 갖는 알고리즘을 설게할 수 있다. 

 

대표적인 예시 : https://eded-hiscalifh.tistory.com/101?category=931269 

Two Sum