둔필승총

알고리즘은 시간과 공간에 따라 평가 된다. 공간이라고 하면 뭔가 내 방 같은 눈에 보이는 공간 느낌이라 이상할 수 있는데 공간은 컴퓨터의 메모리라고 생각하면 된다. 

둘 중 어느 것이 중요하냐고 물어보면 시간을 더 중요하게 여긴다. (알고리즘 문제를 풀더라도.. 보통 시간초과 문제에 머리를 싸멘다..)

메모리는 돈 주고 늘릴 수 있지만, 시간은 그렇지 않기 때문이다. 

 컴퓨터 사양, 프로그래밍 언어에 따라 속도에 차이가 있을 수 있으므로 단순히 프로그램이 돌아가는 시간으로 알고리즘을 평가하기는 어렵다. 그래서 시간복잡도를 이용해서 평가한다.

시간복잡도(Time Complexity)

시간복잡도의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오다.

빅오로 시간복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.

데이터가 많아질수록 걸리는 시간이 얼마나 증가하는가에 따라 결정한다. 시간복잡도를 평가하기위해서는 수학적 개념이 들어간다. 거듭제곱과 로그이다.

내가 보통 Python으로 알고리즘을 풀면, 시간제한은 1초, 2초, (함정으로 0.5초도 가끔 보인다.) 이다. 해당 문제를 해결하려면 시간복잡도를 항상 따져야 한다. 
1초라면 1억번의 연산을 할 수 있다고 생각하고 문제를 풀면 된다. 예를 들어, n이 10000보다 작다면 n제곱까지 고려를 할 수 있다. 시간제한과 n의 값의 범위를 보고 어떤 알고리즘을 사용할지 결정하는데 도움이 된다.

점근 표기법(Big -O Notation)

빅오(O, big-O)란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.

 알고리즘 소요시간은 input 크기에 따라 표현할 수 있다. 점근 표기법이란 소요시간이 20n +40이면 40은 없애주고 앞에 붙은 20도 없애줘서 O(n)으로 그냥 표기하는 것이다. 또 2n^2+8n+157이면 O(n^2)이 되는것이다. 

 점근 표기법의 핵심은 n이 엄청 크다고 가정하는 것이다. n이 별로 크지 않으면, 안 좋은 알고리즘을 써도 상관없다. n이 엄청 큰 경우 알고리즘의 중요함을 느낀다.

O(1) 

input사이즈에 영향을 받지 않는다. input크기와 상관 없이 실행되는 코드만 O(1)이다. 최고의 알고리즘이라 할 수 있다. O(1)에 실행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.

O(logn)

로그는 매우 큰 입력값에도 크게 영향을 받지 않는편. 대표적으로 이진 검색이 이에 해당한다.

def print_powers(n) :
	i=1
    while i<n:
    	print(i)
        i=i*2

O(n)

입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간(Linear-Time) 알고리즘이라고 한다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당한다. 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.

O(nlogn) : O(n)과 O(logn)이 겹쳐진 것

병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(nlogn) 보다 빠를 수 없다. 

def print_powers_of_two_repeatedly(n):
    for i in range(n): # 반복횟수: n에 비례
        j = 1
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2

O(n^2) 

버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.

O(2^n)

피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. n^2보다 2^n이 훨씬 크다.

O(n!)

각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(TSP)를 브루트 포스로 풀이할 때. 가장 느린 알고리즘이다.

공간 복잡도

O(1) 

def product(a, b, c):
    result = a * b * c
    return result

result가 차지하는 메모리 공간은 인풋과 무관하기 때문

O(n)

def get_every_other(my_list):
    every_other = my_list[::2]
    return every_other

my_list의 길이가 n이라고 하면 변수 every_other이 공간을 차지한다. every_other에는 my_list의 짝수 인덱스의 값들이 복사돼서 들어간다. 약 n/2개의 값이 들어간다. O(n)이다.