알고리즘 시간복잡도, 공간복잡도, 점근표기법 / TIL (22-11-10)

알고리즘 강의를 듣기 시작했다.

주어진 과제에 따라 문제를 해결하는 과정은 즐거운데

점점 더 복잡해져서 공부를 열심히 해야겠다는 생각이 든다!

 

시간복잡도

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

입력값이 늘어도 그에 따라 늘어나는 시간소요가 작을수록 좋은 알고리즘.

계산 방법

최대값을 찾는 함수 
각 줄이 실행되는 것을 한번의 연산이 된다고 생각하면 된다.

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)

연산된 것들을 더하면,

array의 길이(N) * array의 길이(N) * 비교연산 1번 = N^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

변수를 선언하는 갯수만큼 공간을 차지하는건가??

아무튼 총 30만큼의 공간이 사용되었다고 말할 수 있겠다.

하지만, 공간복잡도는 상수이기 때문에 입력값과 관련이 있는 시간복잡도와의 우선순위 경쟁에서 밀릴 수 밖에 없다.

 

---

점근표기법

알고리즘의 성능을 수학적으로 표기하여 효율성을 평가하는 방법.

 

종류

1. 빅오(Big-O) 표기법

최악의 성능이 나올 때, 어느 정도의 연산량이 걸릴 것인지에 대해 표기

거의 모든 알고리즘은 빅오 표기법으로 분석한다.

 

2. 빅 오메가(Big-Ω) 표기법

최선의 성능이 나올 때, 어느 정도의 연산량이 걸릴 것인지에 대해 표기

 

---