시간복잡도

 

시간복잡도

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 시간 복잡도가 높다 == 수행 시간이 길다
  • 시간 복잡도가 낮다 == 수행 시간이 짧다
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
  • 공간 복잡도가 높다 == 많은 메모리가 필요하다
  • 공간 복잡도가 낮다 == 많은 메모리가 필요하지 않다

 

가장 빠르게 증가하는 항만 고려하면 된다.(상한)

-> 연산 횟수가 3N^3 + 5N^2 + 1000000이라면 O(N^3)으로 표현

 

- 좋은 것 부터(빠른)

O(1) :상수 시간

O(logN) : 로그 시간

O(N) : 선형 시간

O(NlogN) : 로그 선형 시간

O(N^2) : 이차 시간

O(N^3) : 삼차 시간

O(2^n) : 지수 시간

O(N!) : 팩토리얼 시간

- 나쁜 것 까지(느린)

 

---

 

 

• 코딩 테스트에서 문제의 제한 시간은 일반적으로 1~5초
• 문제 풀기 전, 문제의 시간 복잡도를 확인한다면, 얼마나 효율적인 알고리즘을 작성해야하는지 알 수 있다.
  • 예를 들어, 주어진 N의 범위가 최대 5,000이며, 주어진 제한 시간이 1초라면,
  • 시간 복잡도가 O(N^3)인 알고리즘의 연산 횟수는 10억을 넘어가며, 10초 이상의 시간이 걸리므로, 사용하기 어렵다.
  • ex) 5000 * 5000 * 5000 = 125,000,000,000. 1초에 약 5000만번 정도의 계산을 한다고 하면 약 2500초가 걸리는거다.

---

 

N 의 범위와 시간 복잡도에 따른 연산 횟수

• N 의 범위가 1,000 일 경우 연산량
  • O(N) : 1,000
  • O(NlogN) : 10,000
  • O(N^2) : 1,000,000
  • O(N^3) : 1,000,000,000
• 즉, N 의 범위가 1,000 일 경우, 시간 복잡도가 O(N^2) 이하인 알고리즘을 설계하는게 좋다. (너무 차이난다)

---

 

제한 시간이 1초 일 경우, N 의 범위에 따른 시간 복잡도 선택

• N 의 범위가 500 인 경우
  • 시간 복잡도가 O(N^3) 이하인 알고리즘을 설계
• N 의 범위가 2,000 인 경우
  • 시간 복잡도가 O(N^2) 이하인 알고리즘을 설계
• N 의 범위가 100,000 인 경우
  • 시간 복잡도가 O(NlogN) 이하인 알고리즘을 설계
• N 의 범위가 10,000,000 인 경우
  • 시간 복잡도가 O(N) 이하인 알고리즘을 설계
• N 의 범위가 10,000,000,000 인 경우
  • 시간 복잡도가 O(logN) 이하인 알고리즘을 설계

 

사실 위의 내용이 잘 이해가 안됐다.

 

그래서 좀 더 공부해보니 n으로 구성된 O()를 계산할 때 계산량이 1억번 정도면 1초 정도의 시간이 걸린다고 한다.

( 일반적인 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 1초에 실행할 수 있는 연산량은 1억번 )

정확한 값이 아니고 문제와 알고리즘에 따라 달라질 수 있다.

 

그래서 보통 1초가 걸릴 때 입력 N 범위를 보면

 

100,000,000 : O(N)

10,000 : O(N^2)

500 : O(N^3) ( 500 * 500 * 500 = 125,000,000 )

20 : O(2^N)

10 : O(N!)

위와 같은 느낌적인 느낌이다.

 

 

---

알고리즘 문제 해결 과정

1. 지문 읽기 (문제 하나하나 꼼꼼히 분석해보기, 단계별로 쪼개보기)

2. 요구사항(복잡도) 분석 (어느정도 성능으로 동작하는 프로그램을 작성해야 정답으로 인정되는지)

3. 문제 해결 아이디어 찾기

4. 소스 코드 설계 및 코딩

 

일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제한다고 한다.

 

---

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

 

 

 

---

 

log에 대한 설명