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

개념정리

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

 

 

시간복잡도

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

 

예시1)

input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):         
    for num in array:               # array 의 길이만큼 아래 연산이 실행
        for compare_num in array:   # array 의 길이만큼 아래 연산이 실행
            if num < compare_num:   # 비교 연산 1번 실행
                break
        else:
            return num

result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

1. array의 길이 / X array의 길이 / X 비교 연산 1번 실행

array(입력값)의 길이는 보통 N이라고 표현하며, 위의 시간은 아래와 같이 표현

N × N = N²  #N² 만큼의 시간이 걸렸겠구나!

 

예시2)

def find_max_num(array):
    max_num = array[0]      # 연산 1번 실행
    for num in array:       # array 의 길이만큼 아래 연산이 실행
        if num > max_num:   # 비교 연산 1번 실행
            max_num = num   # 대입 연산 1번 실행
    return max_num

result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888])

1. max_num 대입 연산 1번
2. array의 길이 X (비교 연산 1번 + 대입 연산 1번)

1 + 2 × N   # 2N+1만큼의 시간이 걸렸겠구나!

 

N의 길이에 따른 길이 비교

1. N과 N² 은 N 이 커질수록 더 큰 차이가 나는구나!
2. N의 지수를 먼저 비교하면 되겠구나.
3. 상수는 신경쓰지 않는다.

 

공간복잡도

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계

 

예시1)

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"]
 	# -> 26 개의 공간을 사용합니다
   
    max_occurrence = 0                 # 1개의 공간을 사용합니다
    max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다

    for alphabet in alphabet_array:
        occurrence = 0                 # 1개의 공간을 사용합니다
        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"))

1. alphabet_array 의 길이 = 26
2. max_occurrence, max_alphabet, occurrence 변수 = 3
3. 29만큼의 공간 사용

 

예시2)

def find_max_occurred_alphabet(string):
    alphabet_occurrence_list = [0] * 26    # -> 26 개의 공간을 사용합니다

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')   # 1개의 공간을 사용합니다
        alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0        # 1개의 공간을 사용합니다
    max_alphabet_index = 0    # 1개의 공간을 사용합니다
    for index in range(len(alphabet_occurrence_list)):
        alphabet_occurrence = alphabet_occurrence_list[index]   # 1개의 공간을 사용합니다
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))


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"))

1. alphabet_array 의 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
3. 30만큼의 공간사용

 

29와 30 모두 상수라 큰 상관이 없음, 시간복잡도로 비교

 

 

점근표기법

• 알고리즘의 성능을 수학적으로 표기하는 방법, 알고리즘의 “효율성”을 평가하는 방법
• 떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
• 시간복잡도, 공간복잡도는 점근표기법의 일종
• 종류
  • 빅오(Big-O)표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기 - O(N)
  • 빅 오메가(Big-Ω) 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기 - Ω(1)

input = [3, 5, 6, 1, 2, 4]


def is_number_exist(number, array):
    for element in array:         # array의 길이 만큼 아래 연산 실행
        if number == element:     # 비교 연산 1번 실행
            return True           # N * 1 = N만큼
    return False


result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

• 빅오 표기법 으로 표시하면 O(N)
• 빅 오메가 표기법으로 표시하면 Ω(1)

* 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석