2. 복잡도(Time complexity)

 알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다.

이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 컴파일러의 속도에 달려있다.

 

알고리즘의 실행시간은 두 부분으로 나누어 볼 수 있다.

 

 ㅇ 입력값의 크기에 따라 알고리즘의 실행시간을 검증할 수 있다.

 

 ㅇ 입력값의 크기에 따른 함수의 증가량

   - 중요하지 않은 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데 이것을 점금적 표기법(Asymptotic notation)이라고 부른다.

   - 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미이다.

---

시간 복잡도

 점근적 표기법을 알아보기 전에 시간복잡도라는 것이 무엇인지를 알아보자.

 

 시간 복잡도는 문제를 해결하는 알고리즘의 성능을 표기하는 방법이다.

알고리즘의 로직을 코드로 구현할 때, 시간복잡도를 고려한다는 것은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'라는 말이다.

 

같은 알고리즘이더라도 데이터의 형태가 변하거나, 또 다른 알고리즘과 결합하면서 연산 횟수가 달라지는 경우가 많기 때문에 복잡도는 최악, 최선, 중간의 경우로 나누어서 평가한다.

 

 ㅇ 최상의 경우 : Big-Ω Notation, Ω(n)

   - 빅 오메가 표기법으로 불리며, 최상의 실행시간을 표기한다.

 

 ㅇ 평균의 경우 : Big-θ Notation, θ(n)

   - 빅 세타 표기법으로 불리며, 알고리즘의 평균 실행시간을 표기한다.

 

 ㅇ 최악의 경우 : Big-O Notation, O(n)

   - 최악의 경우를 대비하는 표기법이다.

   - '아무리 최악의 상황이라도 최소한 이 정도의 성능은 보장한다' 라는 의미이기 때문에 가장 많이 사용됨.

빅-오 표기법(Big-O)

 Big-O 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.

 

1️⃣ O(1), 상수 시간

 입력된 데이터의 크기와 관계 없이 일정한 시간이 소요되는 알고리즘의 시간 복잡도를 표현할 때 사용한다.

 

def first_element(arr):
    print(f"배열의 첫 요소는 {arr[0]} 입니다.")

 

2️⃣ O(n), 선형 시간

 입력된 데이터의 크기에 비례해서 처리시간이 늘어나는 알고리즘의 시간 복잡도를 표현할 때 사용한다.입력이 증가하면 처리시간 또는 메모리 사용이 선형적으로 증가한다.

 

def first_element(arr):
    for i in range(len(arr)):
        item = arr[i]
        print(f"배열의 {i}번째 요소는 {item} 입니다.")

 

3️⃣ O(2^n), 지수 시간

 입력된 데이터 크기의 지수 제곱에 비례해서 처리시간이 늘어나는 알고리즘의 시간 복잡도를 표현할 때 사용한다.대표적으로 재귀 함수로 구현한 피보나치 수열이 있다.

 

def fibonacci(num):
	if (num <= 1):
		return num;
	
	return fibonacci(num - 2) + fibonacci(num - 1);

4️⃣ O(nlogn), 선형로그형 문제를 해결하기 위한 단계의 수가 N * (log2N)번 만큼의 수행 시간을 가진다.

 

5️⃣ O(logn), 로그 시간 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

 

종합

 

 Big-O 표기법은 데이터의 입력 개수가 충분히 크다고 가정하기 때문에, 상수항 정도의 사소한 차이는 무시하고 가장 단순한 형태로 표기하도록 규칙을 정했다.

---

공간 복잡도

 공간 복잡도는 프로그램을 실행시킨 후 완료하기까지 필요로 하는 공간의 크기를 의미한다.

 

 ㅇ 고정 공간

   - 코드가 저장되고, 단순한 변수와 상수가 저장되는 공간. (알고리즘과 무관)

 

 ㅇ 가변 공간

   - 코드가 실행되는 도중에 동적으로 필요한 공간. (알고리즘과 연관된 공간)

 

공간 복잡도도 역시 Big-O 표기법을 사용해 입력된 데이터의 크기와 실제 사용하는 공간 사이의 관계를 표현하면 된다.