예1) 6N+5 의 경우, 총 소요시간은 5보다는 6N에 좌우된다.이때 상수 6도 제외하고 그냥 N에 집중하는 것. => O(N) 예2) 2N+10logN의 경우 N이 커질수록 10logN보다는 2N이 훨씬 클테니 2N만 남기고, 상수도 제외함. => O(N) 예3)N2(제곱)+2N+4 => O(N제곱)
시간복잡도
뒤로 갈 수록 시간 복잡도의 차이가 수행시간에 아주 큰 영향을 준다.
이때 O(2의N승) 은 N이 25이하 정도로 아주 작은 수가 아니면 코딩테스트 시간 복잡도를 통과하기 어렵다. 팩토리얼은 그보다 더 큰 폭으로 시간 복잡도가 올라가기 때문에 11이하의 수가 아니면 시간 제한 통과하기가 어렵다.
공간복잡도
: 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
예) 크기 N짜리 2차원 배열이 필요하면 O(N²), 따로 배열이 필요 없으면 O(1)
코테는 보통 시간복잡도 문제를 해결하면 되므로, 메모리 제한이 512MB일 때 int변수를 대략 1.2억개 정도 선언할 수 있다는 것만 기억해두기. (int 1개가 4바이트) -> 떠올린 풀이가 크기가 5억인 배열을 필요로 할 때 해당 풀이는 주어진 메모리 제한을 만족하지 못하므로 틀린 풀이이다!!
정수자료형
int의 최댓값은 21억
Integer Overflow
127에 1을 더하면 ? 컴퓨터 상에서는 01111111에 1을 더한다 -> 10000000이 된다 -> 최대범위보다 커짐.
실수자료형
실수의 저장 및 연산 과정에서는 반드시 오차가 발생한다. -> 실수자료형은 필연적으로 오차가 있으므로, 문제상에서 절대/상대 오차를 허용한다는 단서를 준다. 없다면? 정수자료형을 사용하는 문제일 확률이 높다.
double 에 long 범위의 정수를 담아서는 안된다. 오차가 섞인 값이 저장될 수 있다. int는 담더라도 오차가 생기지 않음.
