[Algorithm] 시간복잡도 / 공간복잡도 / 자료형

1.

시간복잡도(Time Complexity): 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

빅오표기법(Big-O Notation): 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

- "걸리는 시간이 N에 비례한다.", "lg N에 비례한다."라고 표현한 것이 빅오표기법의 역할이다.

 

2.

컴퓨터는 1초에 대략 3-5억 개 정도의 연산을 처리할 수 있다.

N의 크기	허용 시간 복잡도
N <= 11	O(N!)
N <= 25	O(2^N)
N <= 100	O(N^4)
N <=500	O(N^3)
N <=3,000	O(N^2lgN)
N <=5,000	O(N^2)
N <=1,000,000	O(NlgN)
N <= 10,000,000	O(N)
그 이상	O(lgN), O(1)

 

4.

공간복잡도(Space Complexity): 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

512MB = 1.2억개의 int 

 

5. 

정수자료형

- unsigned char에서는 제일 왼쪽이 2^7이고 char에서는 제일 왼쪽이 -2^7이다.

- 10000011을 unsigned char로 읽으면 131이고 char로 읽으면 -125가 되는 것을 확인할 수 있다.

- unsigned char로 표현할 수 있는 수의 최솟값은 00000000일 때 0이고, 최댓값은 11111111일 때 255이다. char로 표현할 수 있는 수의 최솟값은 10000000일 때 -128이고, 최댓값은 01111111일 때 127이다.

- Integer Overflow 주의하기

 

6.

실수자료형

- 2의 음수 거듭제곱을 이용해 임의의 실수를 2진수로 나타낼 수 있다.

-  11101.001(2) = 1.1101001(2)  × 2^4 

- 실수를 나타낼 때 sign field(부호 결정), exponent field(지수 저장), fraction field(유효숫자 저장)로 나누어진다. float는 각 필드의 크기가 1, 8, 23 bit이고 double은 1, 11, 52 bit이다.

 

7.

실수 자료형의 성질

(1) 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.

- fraction field를 보면 float는 유효숫자가 6자리이고 double는 유효숫자가 15자리이므로 float은 상대 오차 10^-6까지 정확하고 double은 10^-15까지 정확하다.

(2) double에 long long 범위의 정수를 담으면 오차가 섞인 값이 저장될 수 있다.

- double은 유효숫자가 15자리인데 long long은 최대 10자리이므로 10^18+1과 10^18을 구분할 수가 없다.

(3) 실수를 비교할 때는 등호를 사용하면 안된다.

- 오차 때문에 두 실수가 같은지 알고 싶을 때에는 대략 10^-12이하면 동일하다고 처리하는 것이 안전하다.

int main(void) {
	double a = 0.1 + 0.1 + 0.1;
    double b = 0.3;
    if(a==b) cout<<"same 1\n";
    if(abs(a-b) < 1e-12) cout << "same 2\n";
}
/***result***
same 2
*************/

 

 

이 글은 바킹독님의 실전 알고리즘을 들으며 공부한 내용을 정리한 글입니다.