자료구조/👉알고리즘 - 4

학습기록

오늘 들은 강의 목록

1. 시간복잡도 - 1
2. 시간복잡도 - 2

알고리즘 복잡도

복잡도가 왜 중간에 있지?

복잡도를 공부하고, 기초적인 자료구조를 배우면 별로 와닿지도 않고 그동안 까먹을 것이다.

강사님이 이렇게 말씀하셨는데, 이런생각을 처음해보는데 이게 맞다.
복잡도를 공부하면 알고리즘을 하면서 “내가 짠 알고리즘의 복잡도는 어떻게 되는가?”라는 생각으로 복잡도를 구해보고, 다른 알고리즘과 복잡도의 차이를 보면 좀 와닿고 기억에도 길게 남게 된다.

그럼 다음은 복잡도란 무슨말일까?

알고리즘에서 복잡도?

알고리즘에서 복잡도란 시간, 공간 복잡도를 말한다.
이는 알고리즘의 효율을 평가하는 기준이 된다.

시간복잡도?

시간복잡도 = 실행 속도

시간복잡도는 하나의 문제를 푸는데 “걸리는 시간”이다.
따라서, 이는 “실행 속도”와 같다.

시간복잡도를 구하는 방법

간단하게 말하면 n에따라 반복문이 반복되는 횟수를 구한다.

이 코드가 얼마나 오래걸리는가?를 구하기 위한 기준을 반복문으로 삼는다.
왜 반복문으로 기준을 잡는가? 라는 질문을 하면, 같은 코드를 반복하는 것이 반복문이고, 코드의 실행시간은 각 코드의 실행시간의 합이다.
반복문은 같은 코드를 반복하여 실행시간을 증가시킨다.
n이 주어질때 반복문이 $log n$번 수행되느냐, $n$번 수행되느냐, $n^2$번 수행되느냐에 따라서 이들의 성능을 결정할 수 있다.

하나의 예로
f1(n)의 복잡도가 100000시간,
f2(n)의 복잡도가 $n^2$시간,
이라 할때,

f1(n)
f2(n)

이러한 프로그램의 시간복잡도는 100000+n^2 시간이겠지만,
n이 100000처럼 매우 커지게되면, 100000시간은 아주 작은 시간이 되어 무시해도 될 정도의 시간이 된다.
이처럼 상수시간은 무시하고, 가장 큰 비중을 차지하는 반복문을 기준으로 잡아서 시간복잡도를 표기하게 된다.

공간복잡도?

공간복잡도 = 메모리 사용량

공간복잡도는 하나의 문제를 푸는데 필요한 “저장공간의 크기”이다.
따라서, 이는 “메모리 사용량”과 같다.

메모리 사용량은 (자료형의 크기 * 사용할 크기)의 합이 된다. 메모리 사용량은 나중에 하지않을까 싶기도 하고, 파이썬이라 안하려나 싶기도..?

성능 표기법 (시간복잡도)

빅 오(Big-O) : O(n)

최악의 실행시간을 표기한다.

상수는 제거하고 표기한다. (다른 표기법들도 마찬가지) n에따라 어느정도로 복잡도가 증가하는지 알기 위함이기 때문에 상수 및 계수는 제거하고 log, 지수등을 이용해서 표기한다.

O($1$), O($log n$), O($n$), O($n log n$), O($n^2$), O($2^n$), O($n!$)등으로 표기한다.

O($1$)을 사용하는 경우는 O(n)에서 n의 자리가 상수일때이다. (n에 따라 시간이 증가하지 않는다는 뜻을 포함하고 있다.)
ex) O(9999) -> O(1)

O($n$)을 사용하는 경우는 O(n)에서 n의 지수가 1일때이다. 계수나 더해지는 상수는 무시한다.
ex) O(3n) -> O(n), O(3n + 10000) -> O(3n)

O($n^k$)을 사용하는 경우는 O(n)에서 n의 지수가 k일때이다.(최약의 실행시간을 표기하므로 지수가 가장 큰 항을 이용해서 표기한다.) ex) O($3n^3 + 2n^2 + n + n log n$) -> O(n^3)

오메가 (Ω) : Ω(n)

최상의 실행시간을 표기한다

세타 (Θ) : Θ(n)

평균 실행시간을 표기한다.

가장 많이 사용하는 빅오 표기법

왜? 빅오 표기법은 최악의 케이스를 대비하는 표기법이다.
알고리즘 문제를 풀때는 한정된 시간과 한정된 메모리에서 최선의 케이스부터 최악의 케이스까지 모두 주어질 것이다.
이때 최선의 코드를 작성하기 위해서는 최악의 케이스를 기준으로 하는 것이 모든 케이스를 통과할 수 있는 코드일 것이다.
그러기 위해서는 내가 작성하는 코드의 최악의 케이스를 해결할때의 시간복잡도를 구해야하는데, 이것이 빅오 표기법으로 구한 시간복잡도이기 때문이다.

빅오 표기법으로 시간복잡도 구하기

강좌에서 나온 1부터 n까지의 합을 구하는 알고리즘을 작성해보자

1. 가장 단순하게 풀이방법 : 반복문으로 1부터 n까지 다 합해서 구한다.

n = 100
sum = 0
for i in range(1, n + 1):
    sum += i
print(sum)

시간복잡도 : O(n)

1. 공식을 이용한 풀이방법 : $\displaystyle\sum_{i=1}^n i = {n(n+1)\over2}$

n = 100
sum = (n * (n + 1)) / 2
print(sum)

시간복잡도 : O(1)

이와 같이 같은 프로그램도 복잡도가 이렇게나 차이가 날 수 있다.

마지막

알고리즘을 한다면 시간복잡도를 구할 수 있어야하고, 중요하다.

강사님께서도 계속 말씀하셨다.
자료구조할때는 그냥 스-윽 지나가도 알골파트로 넘어가면 스-윽 지나가면 안됨!!

시간/공간 복잡도는 다른 알고리즘이나 자료구조와 포스트가 같이 포함되지 않으면 좋겠어서 따로 뺐다. 자료구조 파트지만, 알고리즘에 더 가깝다고 생각해서 알고리즘 카테고리로 넣어야겠다.

아! 그리고 그 $n^3 + n^2$같은 항이 여러개있는 형태에서 최고차항만 본다는 부분이 이해가 안될수 있는데 n이 엄청 커지면 아무리 $n^2$이라도 $n^3$에 비하면 무시해도 될 정도로 엄청 작은 수라서 그런것이다.
(이쪽은 수학?쪽이라 하긴 뭐한데 암튼 수학쪽, 아 마침 말이 나와서 그런데 형상화수학이라고 수학 책도 있고 유튜브도 있는데 수학 좋아하면 꽤 재밌다. 유튜브는 약간 졸릴수이ㅆㅇ…)

다음에 들을 강의

1. 해쉬테이블 - 1
2. 해쉬테이블 - 2
3. 해쉬테이블 - 3
4. 해쉬테이블 - 4
5. 해쉬테이블 - 5

다 들을수 있을지 나눠들어야할지 모르겠다.. 같은 내용은 한번에 듣는게 최고인데 집에 도착하면 7시, 저녁먹고 뭐하다보면 8시,
2배속으로 2번이상 들을텐데 그러면 한 2시간정도 걸리고, 10시? 포스트 2시간 이내로 제출..?
으으.. 되려나 모르겠다.