1장 알고리즘과 입출력 - (2) 시간 복잡도

1. 시간 복잡도

-시간 복잡도를 이용하면 작성한 코드가 시간이 얼마나 걸릴지 예상할 수 있음

-표기법으로 대문자 O 사용

-영어로는 Big O Notation

-입력의 크기에 대해서 시간이 얼마나 걸릴지 나타내는 방법

-최악의 경우에 시간이 얼마나 걸릴지 나타내야 함

[구현 방법에 따른 시간 복잡도]

(예 - 1부터 N까지의 합)

1)O(N)

for(int i=1;i<=N;i++)

sum+=i;

2)O(1)

sum=N*(N+1)/2;

3)O(N^2)

for(int i=1;i<=N;i++){

for(int j=1;j<=N;j++){

if(i==j) sum+=j;

}

}

2. 시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초 정도 

-1억=10^8=약 1초

3. 대표적인 시간 복잡도와 1초가 걸리는 대략적인 입력의 크기 N

-O(1)       

-O(logN)

-O(N)        : 10^8(=1억)

-O(NlogN)  : 5*10^6(=500만)

-O(N^2)    : 10^4(=1만)

-O(N^3)    : 5*10^2(=500)

-O(2^N)    : 20                ex) 크기가 N인 집합의 부분 집합(원소가 N개인 집합이 있고 그 집합의 부분집합의 수 -> 2^N)

-O(N!)       : 10                ex) 크기가 N인 순열(줄 세우는 경우의 수)

-예를 들어 어떤 알고리즘 문제를 푸는데 사용한 알고리즘의 시간복잡도가 O(N^2) 이라면

 입력의 크기 N의 범위가 10^4을 훨씬 넘어가게 되면, 시간 제한이 1초인 경우 다른 알고리즘을 생각해봐야 함

4. 시간 복잡도 계산 시 주의사항

-Big O Notation에서 상수는 버림 

 ex) O(3N^2) = O(N^2)

O(5)=O(1)

-두 가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버림

 ex) O(N^2+N) = O(N^2)

      O(N^2+NlogN) = O(N^2)

-두 가지 항이 있는데 변수가 다르면 놔둠

 ex) O(N^2+M)