[12일차 과제] 시간복잡도, 공간복잡도

1. 복잡도

• 시간복잡도
• 공간복잡도

2. 빅오표기법

3. 5가지 복잡도에 대한 간단한 예제 코드

 

4. 반복문 개수에 따른 시간 복잡도

 

5. 리스트에서 자주 사용하는 함수들의 시간복잡도

 

6. 공간복잡도가 증가하는 상황 예제 코드

 

7. 비효율적인 코드와 효율적인 코드 비교

---

1. 복잡도

• 알고리즘의 성능을 나타내는 척도
• 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘
• 종류 : 시간복잡도와 공간복잡도
• 효율적인 알고리즘을 사용한다는 가정 하에, 시간복잡도와 공간복잡도는 Trade-off 성립
  -> 메모리를 조금 더 많이 사용하면 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 복잡도를 줄일 수 있음

1. 시간복잡도(Time Complexity)

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지 의미
• 알고리즘을 위해 필요한 연산의 횟수
• 빅오표기법을 사용함

2. 공간복잡도(Space Complexity)

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지 의미
• 알고리즘을 위해 필요한 메모리의 양
• 빅오표기법을 사용함
• 공간 복잡도를 따질 때는 "추가로" 사용하는 메모리만 계산
• 구성요소
  1. 고정 공간(Fixed Space)
     • 입력 크기(n)과 관계없이 항상 일정하게 사용하는 메모리
     • 변수, 상수, 코드 자체 등
  2. 가변 공간(variable Space
     • 입력 크기(n)에 따라서 변하는 메모리
     • 동적 할당, 재귀 호출 스택 등

# 매개변수 arr 자체는 제외
# 코드 내부에서 추가로 쓰는 메모리만 계산
def get_max(arr):
	m = arr[0]		# 변수 1개 추가 -> O(1)
    for x in arr:
    	if x > m:
        	m = x
    return m

---

2. 빅오표기법(BIG-O Notation)

• 가장 빠르게 증가하는 항만 고려하는 표기법으로, 함수의 상한만 표시 (아무리 나빠도 이정도)
• 빅오표기법의 규칙
  1. 상수항 무시 : 실행 시간에 영향을 주지 않는 상수는 버림
     ex. O(3n) -> O(n)
  2. 영향력 없는 항 무시 : 가장 증가 속도가 빠른 (차수가 가장 높은) 항만 남김
     ex. O(n² + n) -> O(n²)

점근적 복잡도 표기법 종류
표기법	기호	의미
빅오	O(n)	최악의 경우 (상한)
빅오메가	Ω(n)	최선의 경우 (하한)
빅세타	Θ(n)	평균적인 경우 (상한 + 하한)
리틀오	o(n)	빅오보다 엄격한 상한

 

복잡도 종류 (빠른 순)
표기법	이름	설명	예시 알고리즘
O(1)	상수	입력 크기(n)와 상관 없이 항상 일정한 시간이 걸림	배열 인덱스 접근
O(log n)	로그	입력 크기가 커질 때마다 처리 시간이 로그 비율로 줄어듦	이진 탐색
O(n)	선형	입력 크기에 비례하여 처리 시간 증가	선형 탐색(리스트 전체 탐색)
O(n log n)	선형 로그	입력 크기를 반으로 쪼개 각각 O(log n)의 시간이 걸리는 작업 반복	병합 정렬(정렬알고리즘 중 가장 최선), 퀵 정렬
O(n²)	이차	입력 크기의 제곱에 비례하여 처리 시간 증가 데이터가 많아지면 성능이 급격히 저하	버블 정렬, 삽입 정렬
O(n³)	삼차	입력 크기의 세제곱에 비례하여 처리 시간 증가 데이터가 많아지면 성능이 급격히 저하	행렬 곱셈
O(2ⁿ)	지수	입력 크기에 따라 시간이 기하급수적으로 증가 실무에서는 사용하기 매우 어려움	피보나치 재귀
O(n!)	팩토리얼	모든 경우의 수를 다 따짐	순열 완전 탐색

---

3. 5가지 복잡도에 대한 간단한 예제 코드

1. O(n)

# 배열의 첫 번째 요소에 접근
# 입력 데이터 수가 달라도 항상 1번만 실행
def get_first(arr):
	return arr[0]
    
data1 = [10, 20, 30, 40, 50]
data2 = [11, 20, 30, 40, 50, 60, 70, 80, 90, 100]
print(get_first(data1))
print(get_first(data2))

# 10
# 11

 

2. O(log n)

• 입력한 숫자가 2배 늘어도 연산 횟수가 1회 증가된 것을 확인할 수 있다.

# 숫자를 절반씩 나누다가 1이 되면 종료
# n이 2배 늘어도 반복 횟수는 1번 증가
def cnt_halv(num):
    cnt = 0             # 연산 횟수 저장할 변수

    while num > 1:
        num //= 2       # 절반씩 줄어듦
        cnt += 1
    return cnt

print(f"연산 횟수 : {cnt_halv(37)}")
print(f"연산 횟수 : {cnt_halv(512)}")
print(f"연산 횟수 : {cnt_halv(1024)}")

# 연산 횟수 : 5
# 연산 횟수 : 9
# 연산 횟수 : 10

3. O(n)

• 입력 크기(리스트 크기)가 2배 되었을 때 연산 횟수 2배 증가된 것을 확인할 수 있다.

# 리스트 전체를 순회하여 최댓값을 가져오는 경우
def get_max(arr):
    m = arr[0]       # max값을 저장할 변수(첫 번째 요소로 초기화)
                     # m = 0으로 초기화하면 음수만 있는 리스트에서 에러 발생 
    cnt = 0          # 연산 횟수 저장할 변수

    for li in arr:
        if li > m: 
            m = li
        cnt += 1
    return cnt, m


li1 = [3, 5, 1, 4, 100, 2, 9]
li2 = [3, 5, 1, 4, 101, 2, 9, 30, 50, 10, 40, 99, 20, 90]

cnt1, max1 = get_max(li1)       # 튜플 언패킹 (리턴값 2개를 받아올 변수 2개 사용)
cnt2, max2 = get_max(li2)
print(f"최댓값 : {max1}, 연산 횟수 : {cnt1}")       # 최댓값 : 100, 연산 횟수 : 7
print(f"최댓값 : {max2}, 연산 횟수 : {cnt2}")       # 최댓값 : 101, 연산 횟수 : 14

 

4. O(n log n)

# 숫자를 절반씩 나누는 것을 입력한 데이터 수만큼 실행
def cnt_halv_all(arr):
    cnt = 0             # 연산 횟수 저장할 변수

    for i in arr:
        n = i           # arr 리스트의 요소 1개를 가져와서
        while n > 1:    # 1보다 클 때
            n //= 2     # 2로 나눈다
            cnt += 1
    return cnt

arr = [37, 512, 1024]
print(f"연산 횟수 : {cnt_halv_all(arr)}")    # 연산 횟수 : 24

 

5. O(n²)

# 이중 반복문
# 모든 두 수의 합을 출력 → n × n = n²번 실행

def print_all_hap(arr):
    cnt = 0         # 연산 횟수 저장할 변수

    for i in arr:       # 외부 반복문 n번
        for j in arr:   # 내부 반복문 n번       -> 총 n²번
            print(f"{i} + {j} = {i + j}", end = "   ")      # 각 경우를 모두 출력
            cnt += 1        # 이중 반복문을 도는 동안 연산 횟수 증가
        print()             # 외부 반복문 끝날 때마다 줄바꿈 (보기 좋게 출력하기 위함)
    
    return cnt
            
arr1 = [1, 2, 3]
arr2 = [1, 2, 3, 4, 5, 6]
print(f"연산 횟수 : {print_all_hap(arr1)}")     # 연산 횟수 : 9
print(f"연산 횟수 : {print_all_hap(arr2)}")     # 연산 횟수 : 36

---

4. 반복문 개수에 따른 시간복잡도

1. 단일 반복문 (1개)

• 시간 복잡도 : O(n)
• 내부에서 입력 크기 n만큼 순회
• 데이터가 늘어나는 만큼 연산 횟수도 정비례하여 증가
• ex. 배열의 모든 요소 한 번 탐색

2. 중첩 반복문 (2개)

• 시간 복잡도 : O(n²)
• 바깥쪽 반복문이 n번 돌 때마다 안쪽 반복문이 n번씩 실행되므로 총 n x n번의 연산 수행
• ex. 이중 for문을 사용해 별(*) 찍기

3. k중 반복문 (k개)

• 시간 복잡도 : O(nᵏ)
• 반복문의 깊이가 깊어질수록 (= k가 커질수록) 성능이 급격하게 저하
• ex. 삼중 for문을 사용해 모든 경우의 수를 완전 탐색

---

5. 리스트에서 자주 사용하는 함수들의 시간복잡도

• 리스트는 데이터구조(배열, 연결 리스트)와 사용 언어(파이선, 자바 등)에 따라 시간복잡도가 다르다
• 9일차 과제에서 진행한 단순 연결 리스트의 시간복잡도를 알아보자

단순 연결리스트의 시간복잡도
연산	시간복잡도	설명
맨 뒤 삽입 append	O(n) tail 미사용 시	- 맨 앞 삽입이면 O(1) - 맨 뒤 삽입이면 O(n) : n개의 노드를 모두 순회 후 삭제 가능 - tail 을 사용하게 되면 O(1)로 줄일 수 있으나, tail 관리를 위한 메모리를 사용하게 됨
임의 위치 삽입 insert	O(n)	- 맨 앞 삽입이면 O(1) - 그 외 삽입이면 O(n) : 해당 위치까지 순회하므로
인덱스(위치) 기준 삭제 pop	O(n)	- 맨 앞 삭제면 : O(1) - 그 외 삭제면 : O(n)   -> 단순 연결 리스트는 역방향 참조가 없기 때문에 맨 앞부터 해당 위치까지 순회 필요 - 9일차 과제에서 구현한 단순 연결 리스트에는 pop을 구현하지 않았음
값 기준 삭제 remove	O(n)	- 맨 앞 삭제면 : O(1) - 그 외 삭제면 : O(n)
정렬 sort	O(n²)	- 일반적으로 버블 정렬/삽입 정렬 사용 : O(n²) - 인덱스 접근이 불가해서 -> 퀵/병합 정렬 구현이 복잡함 : O(n log n)

---

 

6. 공간복잡도가 증가하는 상황 예제 코드

• O(1) O(n) O(n²)
• 실제 개발에서는 O(1), O(n)을 가장 많이 사용
• O(n²), O(2ⁿ)은 피하는게 좋음

# O(1) : x는 1개짜리 공간 재사용
for x in arr:
	print(x)
    
# O(n) : result에 계속 추가로 쌓이기 때문에 n개의 요소가 동시에 메모리에 존재하게 된다
result = []
for x in arr:
	result.append(x)

# O(n²) : matrix 리스트에 n개짜리 행이 n번 쌓임
def make_matrix(n):
	matrix = []
    for i in range(n):
    	row = [0] * n			# n개짜리 행이
        maxtrix.append(row)		# n번 쌓임
    return matrix

 

---

7. 비효율적인 코드와 효율적인 코드 비교

• 리스트에서 최댓값 찾는 비효율적 코드 : O(n²)
• 모든 요소를 서로 비교하므로 n x n번 순회

def find max_bad(arr):
	for i in range(len(arr)):
    	is_max = True
        for j in range(len(arr)):
        	if arr[j] > arr[i]:
            	is_max = False
                break
         if is_max:
         	return arr[i]

• 리스트에서 최댓값 찾는 효율적 코드 : O(n)
• 리스트를 한 번만 순회

def find_max_good(arr):
	max_val = arr[0]		# 첫 번째 값을 우선 max_val에 넣음
    for x in arr:			# arr을 돌면서 
    	if x > max_val:		# 각 요소를 비교
        	max_val = x		# 더 크면 max_val 최댓값 업데이트
    return max_val

---

* 복잡도 표기법은 위에 조사한 내용보다 더 많이 있음

* 자료구조 과제 시 배열, 스택, 큐, 연결리스트 관련 포스터에 각각의 시간복잡도 확인 가능

* 공간복잡도의 코드에서 for문의 변수 x는 반복문이 끝나면 메모리에서 해제되기 때문에 공간복잡도로 계산하지 않은지 궁금해서 알아보았다. 결론은 x가 동시에 하나만 존재하기 때문이다. for문 10번 반복해도 x라는 변수 1개짜리 공간만 재사용하기 때문에 여러 개의 x가 메모리에 존재하는 것이 아니기 때문에 O(1) 상수 공간으로 본다.