시간복잡도, 공간복잡도, 오버플로우

* 시간 복잡도

• 알고리즘의 최악의 경우 실행시간
• 입력량 N에 비례해서 얼마나 연산을 많이 하는지를 나타냄
• 빅오 표기법 (Big-O notation)으로 나타냄
• 알고리즘의 효율성 척도
• C++ 기준 1초에 연산 1억 번이 넘어가면 위험 (1초 = 1억)

Big-O 표기법

 

 

---

* 공간 복잡도

• N에 비례해서 메모리를 얼마나 사용하는지를 나타냄
• 메모리(공간)과 시간은 Trade Off 관계

---

 

Ex) 시간제한 2초, 메모리 제한 64MB, 입력 N의 범위는 0 <= N <= 100,000,000

=> N 제곱은 10의 16이 되므로 통과 X,  logN은 통과 O

 

Ex) 시간제한 1초, 메모리 제한 128MB, 입력 N의 범위는 -1000 <= N <= 1000

=> N의 크기는 2000, 시간제한은 1초이기에 연산량은 1억번 가능

=> 따라서 O(N)은 가능, O(N제곱)도 가능

 

---

* 오버플로우

• 자료형이 담을 수 있는 범위를 초과한 값을 넣을 때 발생하는 문제
• Python은 고려하지 않아도 됨
• 기업 코딩테스트에서 오버플로우가 날 수 있는 문제는 잘 나오지 않는 편