학습내용

• 알고리즘
  • 시간 복잡도
  • 공간 복잡도
  • 점근 표기법

시간 복잡도

문제 해결에 관한 입력값과 시간의 상관관계로 알고리즘의 핵심이라고 할 수 있다. 이때 '시간'은 초단위, 분단위 같은 개념이 아닌 절차를 의미한다. 시간과 생산성은 반비례하기 때문에 개발자라면 반드시 이해해야 하는 개념이다.

Big-O 표기법
알고리즘의 효율성을 나타내는 표기법의 일종으로 시간 복잡도 개념을 이해하기에 가장 수월한 방법이다. 이때 N은 입력값, 즉 데이터의 갯수를 의미한다.

O(1) = 상수시간(Constant time)

def print_first(arr):
	print(arr[0])

코드 한 줄은 1번의 연산과 같다. 즉, 위 코드는 1번의 연산만을 거치는 코드다. 이런 함수의 시간복잡도를 상수 시간(Constant time)이라고 한다. 배열에 몇 가지 요소가 들어오든 한 줄로 연산을 완료할 수 있기 때문이다. 입력값의 영향을 받지 않는 특성때문에 가장 선호되는 알고리즘이다.

def print_first(arr):
	print(arr[0])
    print(arr[0])

이 경우에는 코드가 두 줄이므로 2번을 실행한다. 그러나 Big O에서는 이 또한 1번으로 추산한다. Big O는 입력값에 따른 함수의 작동 원리에만 관심 있기 때문이다. 즉, 상수의 영향을 받지 않는다. 예를 들어서 언제나 10번의 절차를 걸쳐야 하는 함수가 있다면 이 함수의 시간복잡도는 O(10)이 아니라 O(1)이다. 입력값이 어떻든간에 값을 구하기 위한 절차는 변하지 않기 때문이다. 단, 상수값이 과도하게 커진다면 영향을 받는다.

O(N) = 선형시간(Linear Time)

def print_all(arr):
	for n in arr:
    	print(n)

위 함수는 배열의 요소가 10개라면 10번을 절차를 밟아야 한다. 즉, 입력값의 영향을 받는다.

def print_all(arr):
	for n in arr:
    	print(n)
    for n in arr:
    	print(n)

마찬가지로 똑같은 함수를 두 번 실행하고 있으므로 O(2N)이 되어야 하지만 상수의 영향을 받지 않으므로 O(N)이 된다. 큰 원리(=인풋값이 증가하면 절차가 증가하는 원리)는 변하지 않았기 때문이다.

O(N²) = 2차 시간(Quadratic Time)

def print_twice(arr):
	for n in arr:
    	for x in arr:
        	print(x, n)

입력값이 10개라고 가정했을 때 이중반복문에서는 100번의 절차를 거쳐야 한다. 반복문 안에서 또 다시 반복문을 실행하기 때문에 10x10의 과정을 거치기 때문이다.

O(log N) = 로그 시간(Logarithmic Time)

프로세스의 스텝을 절반으로 나눠서 진행하는 방식. 입력값이 두 배로 증가해도 처리하는 절차는 한 단계만 증가하는 효율적인 처리 방법이다. 단, 배열의 순서를 바탕으로 처리하기 때문에 정렬되지 않은 배열에선 사용할 수 없다. 이진검색 알고리즘이 여기에 해당된다.

O(1) > O(log N) > O(N) > O(N²)
정리하면 해당 순서에서 왼쪽으로 갈수록 효율적인 알고리즘이라고 할 수 있다.

참조영상
노마드코더
Array 배열 기초개념? 10분안에 정리해줌!
검색 알고리즘? 기초개념 잡아드림. 10분 순삭.
개발자라면 이제는 알아야하는 Big O 설명해드림. 10분컷.

---

공간 복잡도

문제 해결에 관한 입력값과 공간의 상관관계. 공간 복잡도 내에서는 데이터의 갯수보다는 데이터의 크기가 더 큰 영향을 미친다. 그러나 알고리즘 전체에 있어서는 공간 복잡도보다 시간 복잡도의 영향이 훨씬 크다.

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  

공간 복잡도에서는 저장하는 데이터의 양이 1개의 공간을 사용한다. alphabet_array의 길이는 26이고 그 아래로 총 3개의 변수가 있으므로 해당 코드는 29개의 공간이 사용된 셈이다. 이 공간이 바로 상수인데 시간 복잡도에서 상수는 영향을 미치지 못하므로 공간 복잡도보다 시간 복잡도가 훨씬 더 중요한 것이다.

점근 표기법

알고리즘의 효율성을 나타내는 표기법으로 크게 Big-O 표기법과 Big-Ω 표기법으로 나뉜다. Big-O 표기법은 최악의 성능(O(N))을 가정하고 Big-Ω 표기법은 최선의 성능(Ω(1))을 가정하고 접근한다.

표기법은 왜 나뉠까?
입력값이 5개인 배열에서 a를 출력한다고 가정해보자. 만약 a가 0번째 요소에 해당된다면 배열을 모두 돌지 않고 한 번만 돌아도 반환할 수 있다. 이와같은 경우 때문에 Big-Ω 표기법이 존재하는 것이다. 그러나 실제로는 최선보다는 최악의 경우가 훨씬 많기 때문에 Big-Ω 표기법은 사용하지 않는다.

지금까지 배운 내용을 바탕으로 알고리즘을 구현할 때는 Big-O 표기법을 염두해둔채 시간 복잡도를 줄이기 위해 고민해야 한다.

자료구조 선택시 고려사항
1. 삽입시간
2. 삭제시간
3. 검색시간
4. 정렬여부

---

하.... 오늘도 빡셌다.... 강사님이 설명해주시는 코드가 이해 안가는 건 아닌데 혼자서 해결하려고 하면 어떻게 해야할 지를 모르겠고, 접근법을 알아도 코드로 구현을 못한다... 언어를 배울 때는 이해가 안돼도 코드를 따라치다보면 어느 순간 이해가 됐었는데 알고리즘은 그런 방식이 안통하는 것 같다. 기출문제 풀 듯이 온갖 유형별 접근법을 다 공부하고나면 좀 수월해질까? 갈 길이 정말 태산같다 후.... 빨리 프로젝트 하고싶다.........