코드스테이츠 - 시간복잡도

kwak woojong·2022년 5월 31일
0

코드스테이츠

목록 보기
18/36
post-thumbnail

알고리즘을 풀다보면 다양한 풀이법이 나온다. 보통은 직관적으로 풀다가 테스트케이스에서 시간초과보고 박살 난 뒤에 털리는데, 이 시간복잡도를 예상하고 푼다면 어느정도 해결될 수 있다.

이 시간복잡도의 중요 개념은 케이스가 많거나 클 경우 시간복잡도에 따라 기하급수적으로 처리 시간이 늘어난다는 것이다.

상기 그림을 보면 O(n!)은 요소가 조그만 늘어나도 수직상승하고, O(2n)도 마찬가지다.

체스판 1칸에 쌀 1톨을 올리는데, 다음 칸마다 2배씩 늘려 잡으면 263이 된다.

Big-O 표기법

알고리즘이 있는데, 얘가 찾을 데이터의 양과 시간과의 상관관계를 표현한 것이 바로 Big-O 표기법이다.

실제 러닝타임을 측정한다기 보단, 상관관계를 좀 더 중점으로 보기 때문에 간략하게 표기되며, 몇몇 경우는 실제 러닝타임에선 더 걸릴 순 있으나, 표기상으론 통일하는 경우가 있다.

기본 표기는 O(1)이고 이 1이 n으로 바뀌고 팩토리얼이 붙고 지수가 되던가 지수가 붙던가 한다.

O(1)이 가장 기본적인 시간복잡도고, 여기서 알고리즘에 따라

가로측(요소), 세로(시간)을 가진 그래프의 기울기가 바뀐다.


O(1)

변수 하나를 불러서 뭔지 물어보면 걔가 얘다.

요소가 100개든 뭐든 변수 1개만 부르면 되므로, 사실상 요소가 늘어나는 것과 상관 없이 항상 일정한 시간이 걸린다.

얘가 모여서 O(n)되고 하는거지 뭐


O(log n)

이중탐색을 한다고 하자. 근데 O(nlogn)얘와 다르게 어떤 데이터를 찾기만 하면 끝나는 알고리즘일 경우 O(logn)이다.

O(nlogn)얘는 이중탐색을 하고 또 그걸 다 정렬
O(logn)얘는 이중탐색을 하기만 하고 종료!

시간 복잡도도 얼마 안든다. 매우 뛰어난 방식임


O(n)

배열을 한번만 싹 돌면 O(n)이라 보면 된다.

for(int i = 0; i < n; i++) {
	sum += i;
}

요소가 늘어남에 따라 시간도 요소만큼 늘어난다.

어? 맨 윗 그림은 안그렇게 생겼는데요?

걔들은 O(n2), O(2n), O(n!) 의 차이를 좀 더 가시적으로 표기하기 위해 저렇게 그린거고 실제 그래프는 이런 느낌

O(n)은 요소가 1개 증가하면 봐야 할 데이터도 1개 증가하기 때문에 기울기가 1인 그래프를 그린다.


O(n log n)

반씩 짤라서 보는 방식으로 어떤 알고리즘을 만들었다. 근데 그걸 n회 반복하면?

그게 O(n log n)이다. 뭐가 있냐고?

어떤 배열을 순차적으로 정렬을 하는데, 크고 작은지 확인하고, 왼쪽 오른쪽으로 보내면 lon n일테고, 이걸 계속 반복해줘서 정렬을 완성해야 하니까 n회 반복한다.

그럼 그게 O(nlogn)이라 할 수 있다. 이진트리로 나누고, 병합 하는 과정을 생각하면 편할 듯

즉 O(logn)이 n회 반복 되는 것이 예상될 경우 O(nlogn)이라 볼 수 있다.


O(n2)

for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
    	sum = i + j;
    }
}

2중 중첩 반복문을 이런 방식으로 썼을 때, O(n2)가 나온다.

알고리즘시 중첩 반복문은 보통 많이 쓰는 경향이 있다.

만약 다른 방식이 있다면, 지양해야 할 방법이긴 함.

다만 n까지 전체 순회를 하는 방식이므로 변수 제한사항에 따라 조금 갈릴 수 있다.

n은 0 ~ 1천만이고
m이 0 ~ 10인 알고리즘이 있고, 상기 중첩 반복문을 쓴다고 하면

n * m 은 1억이므로 0 ~ 1억개의 요소가 생기는거다.

for(int i = 0; i < n; i++) {
	for(int j = 0; j < m; j++) {
    	sum = i + j;
    }
}

이럴 경우 O(n2)라고 적용하긴 애매하다. 빅오표기법이 대충 최악의 경우를 적는 것이라곤 해도 1천만의 제곱과 1억의 차이는 너무 나잖아? 이럴 경우 차라리

O(nm) 으로 적어주면 보기가 쉽다.

만약 그럴 경우는 거의 없지만 3중 중첩 반복문을 사용할 경우는 어떻게 되는가?

for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
    	for(int k = 0; k < n; k++) }
        	sum = i + j + k;
        }
	}
}

정확히 보자면 O(n3)으로 계산할 수 있겠다.

근데 이미 O(n2)이것도 미친 시간복잡도를 가지고 있기 때문에, O(n3)이게 예상되면 걍 알고리즘 다시 짜야 한다.

n값이 충분히 작다면 고려해볼순 있다.

O(n2)가 반복되는 놈이라면 O(n2 + n2)인가? 라는 고려는 굳이 안해도 된다.
이 경우도 n2을 채기한다. 빅오는 실제 알고리즘의 러닝타임을 재기 위한 방식이 아니라, 숫자가 높아짐에 따라 처리시간의 증가율을 고려하는 표기법 이기 때문에, O(n2 + n2)이거나 O(n2)는 실제 러닝타임은 다르겠지만 증가율을 고려하면 비슷하기 때문인듯


O(2n)

피보나치 수열을 만드는 로직이 대표적이다. 아무런 보조 도움 없이 정확히 피보나치 수열을 만드는 재귀를 짠다면 말이다.

배열, 동적프로그램 방식으로 코드를 짜지 않는 이상 피보나치는 O(2n)이 된다.

체스판의 쌀알 일화를 생각해보면 30~50 이상만 되더라도 엄청 거대한 숫자가 나온다.


O(n!)

팩토리얼로 배열을 순회한다면 그게 O(n!)이다.

이 방식의 경우 매우 느리고, 숫자가 크다면 실질적으로 처리가 불가능에 가깝다.

만약 길이가 100인 배열이 있다고 한다.

어떤 알고리즘을 짜는데, 100의 순회를 끝내고 다음엔 99의 순회, 98회 순회를 순차적으로 하며 최종적으로 1의 순회를 한다고 하자

그럼 100 99 98 --- 즉 N!가 된다.

이럴 경우는 거의 없다. 실무에서 쓰는 논리가 이런 방식이면 직장상사, 고객에게 바로 죽통이 털릴듯

아마 회귀를 더럽게 짜면 이게 될 거 같긴한데... 정확하진 않다.


대표 Big-O 표

profile
https://crazyleader.notion.site/Crazykwak-36c7ffc9d32e4e83b325da26ed8d1728?pvs=4<-- 포트폴리오

0개의 댓글