시간복잡도(Time Complexity)
입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관관계
cf) 허용 시간복잡도
| N의 크기 | 허용 시간복잡도 |
| N ≤ 11 | O(N!) |
| N ≤ 25 | O(2^N) |
| N ≤ 100 | O(N⁴) |
| N ≤ 500 | O(N³) |
| N ≤ 3000 | O(N²logN) |
| N ≤ 5000 | O(N²) |
| N ≤ 1000000 | O(NlogN) |
| N ≤ 10000000 | O(N) |
| 그 이상 | O(logN), O(1) |
빅오표기법
주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
ex) O(N) = 5N + 3
공간복잡도(Space Complexity)
입력의 크기와 문제를 해결하는 데 필요한 공간의 상관관계
ex) 별도의 배열이 필요없는 경우 → O(N)
크기가 N인 배열을 사용하는 경우 → O(N²)
보통 메모리 제한이 512mb라면 약 1.2억개의 int(4바이트) 변수를 사용할 수 있음
실수 자료형
- sign: 부호(0이면 +, 1이면 -)
- exponent: 지수(지수 + 127)
- fraction: 가수
ex) -6.75 = -1.1011(2) * 2²
→ sign = 1 / exponent = 10000001 / fraction = 1011000...00
실수 자료형의 특징
1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수밖에 없음
float(유효숫자 6자리) 대신 double(유효숫자 15자리) 사용
구조체는 call by value 방식으로 파라미터 전달