시간복잡도에 대해서 알고가자 크흐흡

문명주의 자료를 이제야 다시보네 고마워요 명주맨

 

코테를 급하게 준비하며 명주글을 다시본다 흐흐흑 힘들어 코테 없어졌으면 좋겠다.

 

https://medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80-%EB%AF%B8%EC%B9%9C%EC%A7%93%EC%9D%B4%EB%8B%A4/2-%EC%8B%9C%EA%B3%B5%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84%EC%99%80-%EC%9E%85%EC%B6%9C%EB%A0%A5-1df25ebaeede

_2_ 시공간복잡도와

 

내가 보는 자료여서 내가 필요한 것들만 정리하고 넘어가려고 한다 -> 요약요약

 

1. 시간복잡도는 Big O 표기법을 사용한다

가장 큰 연산으로 잡아 먹는거에다가 기준을 두겠다는 것이다.

연산 횟수가 2N 이면 앞에 상수 2는 무시해버린다 결론적으로 횟수를 대략 N으로 다 표시해 버린다.

 

그냥 빅오로 표기하는거에 실제 문제에서 나오는 n을 집어넣어봐서 대략적인 계산 횟수를 계산기로 직접 계산해야한다.

그래서 기준을 넘기는지 아닌지 판단하고 어떤 알고리즘을 적용할지 생각해 봐야할것이다.

 

알고리즘 채점서버는 대략 1초에 1억번 연산이 가능하다고 한다.

그래서 문제에서 주는 초 *1억 그리고 빅오에 n을 넣고 계산해서 비교해봐서 풀수있는지 판단해야한다.

 

 

각 기초적인 연산들은 일단 O(1)이다

->입출력 이런거 상수 많이 붙어서 오래걸리지만 코테 수준에서 상수 컷팅할일 없다.

 

빅오 표기법 계산법 (대략)

일단 O(1), O(N), O(N²) 같은경우는 직관적이다 for문 도는 횟수에 따라서 결정되는것이다.

 

근데 O(2^N) ,O(logN) 이것들은 직관적으로 안들어온다 경우의 예시들을 명주가 정리해놓았다. 그걸보자

 

O(2^N)

우리가 길이 100짜리 배열을 갖고 있고 각 칸을 1이나 0으로 채우는 경우의 수를 센다고 생각해봅시다.
첫 번째 칸이 1이나 0으로 채워지는 경우의 수는 2입니다.
두 번째 칸까지 채운다면 첫 번째 칸에 2가지 경우의 수로 나뉘었으므로 2 * 2 해서 4가 됩니다.
결국, 100번째 자리까지 채우면 2¹⁰⁰ 이 되는 것이죠!
이 때의 배열의 칸 수를 N이라고 한다면 모든 경우의 수를 보기 위한 시간복잡도 빅오 표기법은 O(2^N)이 됩니다!

이런 경우의 수 같은거?

->N 이 26 까지는 커버될것이다.

 

O(logN)

결론 로그는 작아서 무슨 수가 들어가도 딱히 넘을일이 없다.

 

이제 각각 뭐 시간 복잡도 같은거 앞으로 계산해서 써보자 그냥 무지성으로 타임오버내지말고