시간복잡도 (Time Complexity)

• 작성한 코드가 시간이 얼마나 걸리는지 나타내는 방법
• 표기법으로는 Big O Notation
• 입력의 크기(N,데이터의 수)에 대해 시간이 얼마나 걸릴지 나타내는 지표
• 최악의 경우 얼마나 시간이 걸릴지 예상해보며, 다른 효율적인 방법을 찾기 위해 사용하게 된다.

대표적인 시간 복잡도 및 시간 복잡도의 의미

알고리즘 문제에는 시간제한이 있으며, 실제 프로그래밍 시에도 오래 걸리는 프로그램은 퀄리티가 떨어지므로 시간복잡도 즉, 수행 시간을 추정해보는 과정은 중요하다.

[ 대표적인 시간 복잡도 / 시간 복잡도의 의미(풀이 유형) ]

> 알고리즘 문제에는 시간제한이 있으며, 실제 프로그래밍 시에도 오래 걸리는 프로그램은 퀄리티(제품성)가 떨어지므로

시간 복잡도 즉, 수행 시간을 추정해보는 과정은 중요하다.

> 다음의 대표적인 시간 복잡도를 알아보며, 대표적인 문제상황과 그 예상 수행 시간을 추정해볼 수 있다.

> 다음에서 N은 입력 데이터를 일반화한 값으로, N=1억(10^8)이면, 대략 수행 시간은 1초가 걸린다.

> 즉, 문제에서 주어진 가장 큰 입력 범위를 N에 넣었을 때 1억 정도가 나온다면, 그 알고리즘은 유효하다.

> 시간 복잡도 : N에 넣을 수 있는 최대 유효값(결과가 1억 근사치로 나오는 값) // 해당 시간 복잡도의 의미(풀이 유형)

- O(1) : SKIP // 단순 계산(a+b와 같은 연산, 배열에 접근하는 연산)

- O(lgN) : SKIP // N 개를 절반으로 계속해서 나눔

- O(NlgN) : 5백만 //

- O(N) : 1억 // 1중 for 문

- O(N^2) : 1만 // 2중 for 문

- O(N^3) : 500 // 3중 for 문

- O(2^N) : 20 // 크기가 N인 집합의 부분 집합

- O(N!) : 10 // 크기가 N인 수열

* ‘//’ 뒤에 적힌 시간 복잡도의 의미는 대부분 저 시간 복잡도에 해당하는 ‘대부분’의 경우(풀이 유형)를 의미하며, ‘항상’ 유효하다는 의미는 아니다.

* [ 시간 복잡도의 의미(풀이 유형)를 알아두는 것은 중요한 이유 ]는

\0. 알고리즘을 구현하기 전,

\1. 어떻게 구현해야겠다를 결정한 뒤

\2. 시간 복잡도를 계산하여 생각한 알고리즘이 제한 시간 안에 처리 가능한지 확인 후

\3. 프로그래밍하는 것이 중요하기 때문이다. // 소중한 개발 시간을 낭비하지 않기 위해

[ 시간 복잡도 계산 방법(의 유형) ]

> Big O Notation에서 상수는 버린다.

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

> 두 가지 항이 있는데 변수가 다르면 놔둔다.

Ex. O(N*M)