시간 복잡도

시간복잡도 개념

https://joshuajangblog.wordpress.com/tag/시간복잡도-계산/

마지막 두 문장이 좋은 듯 하다.

  • 문제를 해결하려고 할 때마다 시간복잡도를 분석하는 습관을 들이면 좋은 개발자가 될 수 있습니다.
  • 엔지니어에게 있어서, 문제라는 것은 정답이나 최선의 답의 관점에서 접근하는 것보다, 상황에 더 맞는 답인지 아닌지의 관점에서 접근해야 합니다.

종류

O(1) : 단순 계산(a+b, 배열 접근 등)
O(logN) : N개를 계속 절반으로 나눔
O(N) : 1중 for문
O(NlogN)
O(N^2) : 2중 for문
O(N^3) : 3중 for문
O(2^N) : 크기가 N인 집합의 부분 집합
O(N!) : 크기가 N인 순열

1 2 3 … N 이고, N개를 모두 다해야 하는데 순서가 중요할 때

계산

  1. Big O Notation에서 상수는 버린다
    • O(3N^2) : O(N^2)
    • O(1/2N^2) : O(N^2)
    • O(5) = O(1)
  2. 두 가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버린다
    • O(N^2 + N) = O(N^2) : 큰쪽이 월등이 크기 때문에 작은쪽이 별 영향을 미치지 못한다
    • O(N^2 + NlogN) = O(N^2)
  3. 두 가지 항이 있는데 변수가 다르면 놔둔다
    • O(N^2 + M) : 어느쪽이 더 크다고 할 수 없기 때문에

1부터 N까지 합을 계산하는 소스

  1. O(N) : N번 돈다
1
2
3
4
int sum = 0;
for(int i=i; i<=N; i++){
sum += i;
}
  1. O(1) : 수식이 하나다
    int sum = 0;
    sum = N * (N+1) / 2;

  2. O(N^2) : O(N)을 N번 수행하므로 N * O(N) = O(N^2)

1
2
3
4
5
6
7
8
9
10
int sum = 0;
for(int i=1; i<=N; i++){
// O(N) 부분
for(int j=1; j<=N; j++){
if(i==j){
sum += j;
}
}
//
}

적용

시간 복잡도 안에 가장 큰 입력범위를 넣었을 때, 1억 정도가 나오는지 체크해보면 된다(1억 정도 나오는데 1초 정도 걸린다고 가정한다)
다음은 시간복잡도에 대해 1억이 되려면 입력값이 어느 정도까지 가능한지를 나열한 것이다.

  • O(1)
  • O(logN)
  • O(N) : 1억
  • O(NlogN) : 5백만
  • O(N^2) : 1만
  • O(N^3) : 500 // 1.25억
  • O(2^N) : 23 //
  • O(N!) : 10 // 360만

즉, 알고리즘을 어떻게 만들지 구상해보고, 시간 복잡도가 어떤 형태로 나오는지 체크해본다.
그리고 해당 문제의 최대 입력값을 위의 리스트와 비교해보고, 해당 알고리즘으로 문제를 풀 수 있는지 체크할 수 있다.
예를들어 작성한 알고리즘이 N^3인데, 입력의 최대값이 10000까지면 그 알고리즘으로는 해당 문제를 풀 수 없는 것이다.
1초에 수행할 수 있는 횟수?
1억의 input을 넣었을 때 1초가 걸린다?

시간 복잡도를 아는것은 중요하다.
구현을 하기전에 어떻게 구현을 해야곘다고 생각해보고
거기서 시간 복잡도를 계산해본 다음에
이게 문제의 시간 제한안에 나오니까 구현하면 되곘다. 라는것이 중요하다.

추가 자료

나무위키

https://namu.wiki/w/시간 복잡도

좀 더 상세한 정리(+계산법)

http://skmagic.tistory.com/164
https://b-jay.tistory.com/110

반복과 재귀의 시간복잡도 계산법

https://gist.github.com/dobestan/10785328