시간복잡도/공간복잡도/점근표기법

작년 학교 강의를 통해서 알고리즘을 조금 찍먹만 해보았지만,

이 3가지 개념은 정말 수업 내내 나타났기 때문에 이번에는 제대로 공부하고 정리해보았다.

 

시간 복잡도 개념

시간 복잡도란? : 알고리즘이 문제를 풀기 위한 시간(혹은 연산)을 말한다.

단어로 말하자면 "수행시간"

 

우리가 프로그래머스에서 문제를 풀 때 문제를 해결하는 시간이 아래에 뜨는데,

이것이 시간복잡도를 간접적으로 나타내어 준다.

테스트 1의 0.03ms가 내 코드의 시간복잡도이다.

참고로 옆의 10.2MB는 공간복잡도!

 

 

시간 복잡도 풀이법

그렇다면 이 시간복잡도는 어떤 방식으로 구하는 걸까?

 

아래의 예시를 보면 금방 이해될 것이다.

    for num in array:              # array 의 길이(N)만큼 아래 연산이 실행
        for compare_num in array:  # array 의 길이(N)만큼 아래 연산이 실행
            if num < compare_num:  # 비교 연산 1번 실행
                break
        else:
            return num
            
# 연산 과정(시간 복잡도): array의 길이 * array의 길이 * 비교 연산
# == N*N*1 
# == N**2

또 다른 풀이로도 계산해보면

max_num = array[0]     # 연산 1번 실행
for num in array:      # array 의 길이만큼 아래 연산이 실행
	if num > max_num:  # 비교 연산 1번 실행
		max_num = num  # 대입 연산 1번 실행
                
                
# max_num 대입 연산 + {array의 길이 X (비교 연산 1번 + 대입 연산 1번)}
# == 1 + N * 2
# == 2N + 1

각각 (N제곱)과 (2N+1)로 복잡도가 나온다.

그럼 우리는 더 빠른 방법으로 문제를 해결해야 하는데, 어떤 식이 더 빨리 풀릴까?

처음에나 왼쪽이 근소하게 유리했지, N의 숫자가 커질수록 2N+1이 압도적으로 시간에 있어 유리함을 알 수 있다.

 

이 식을 통해 느끼는 것은

변수 N 앞에 붙는 상수들은 아무런 의미가 없다.

2N이나 2N+1이나 N의 숫자가 커질 때는 무의미한 차이(점점 차지하는 비중이 0%에 수렴하게 됨)이기 때문에

비교를 할 때 순서는

1. 제곱 여부 > 2. 계수 여부 (ex) 2N, 5N) > 3. 상수

사실상 제곱 여부만 보면 된다! 2번과 3번은 사실상 무의미

공간복잡도

 

공간복잡도란? : 프로그램의 성능을 분석하는 방법 중 하나로,

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

최근에 좋은 메모리가 많이 등장해서 중요도가 크게 줄었다지만, 그래도 알아두면 좋다.

 

아래 함수에서 메모리를 차지하는 것으로는 어떤 것이 있을까?

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

바로 다음과 같은 것들이 메모리를 차지한다고 볼 수 있다.

(코드블럭 내부에는 밑줄이나 글씨 굵기 조절 못 하는걸까..)

alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]
	# -> 26 개의 공간을 사용합니다
max_occurrence = 0 # 1개의 공간을 사용합니다
max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다.

for alphabet in alphabet_array:
    occurrence = 0  # 1개의 공간을 사용합니다

 

공간복잡도의 효율성 비교도 시간복잡도와 마찬가지로 따진다.

 

점근 표기법

 

점근표기법 : 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법

                     알고리즘의 성능을 수학적으로 표기하여 알고리즘의 효율성을 따지는 데 쓰이는 표기법.

 

빅오 표기법 : 최악의 경우에 어느 정도의 연산량이 나오는가?(시간복잡도의 최댓값)

빅오메가 표기법 : 최선의 경우에 어느 정도의 연산량이 나오는가?(시간복잡도의 최솟값)

 

대부분의 경우에서 우리는 최악의 경우를 대비해야 하기 때문에 주로 빅오 표기법을 사용

 

빅오의 시간복잡도는 다음과 같다.

f(n) = O(g(n))

 

빅오 표기법의 특징은 다음과 같다.

1. 최고차항만 표기 2. 계수 무시 3. 상수 무시

위에서 말한 것처럼, 시간복잡도에 영향력이 0에 수렴하는 계수와 상수는 무시하는 것이다.

이에 따라 시간복잡도가 O(4N^3+6N^2+N+5) 일 경우, O(N^3)으로 표기한다.