공간복잡도

참고자료 : https://blog.encrypted.gg/922

 

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

이 크기는 메모리의 크기를 의미한다.

 

참고 : 512mb = 1.2억개의 int ( int 1개가 4바이트 )

참고 : char 자료형은 1byte = 8bit ( c언어 기준, 자바는 2byte )

 

N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1)

 

예상한 코드가 제한이상의 메모리를 요한다면 다른 방법을 고민해보도록 하자.

 

이러한 1byte는 0,1 즉 이진수가 하나 들어가는 공간이다.

 

int는 byte의 공간을 갖는데 2^31-1개의 숫자를 표현할 수 있다.

2147483647로 21억 정도의 숫자이다.

즉, 이를 벗어난 숫자를 int로 다룰 수 없는 것이다.

 

이걸 초과해서 21억 * 2의 숫자를 int로 다루게되면, 형제약이 뚜렷한 자바의 경우 예외가 나타나 초기화하지 못하거나

의문의 음수가 나타나게 된다.

 

		int a = 2147483647;
		a *= 2;
		
//		int b = 21474836472147483647;
		
		System.out.println(a);

위의 코드처럼 하게되면 b는 오류가 나고, a는 -2로 나타난다.

이는 overFlow가 발생한 것으로 2147483647에서 1증가하게 되면 -2147483648으로 int의 제일 작은수로

돌아가게된다.

숫자가 -2147483648부터 2147483647까지 순서대로 적힌 긴 띠를 순환한다고 상상하면 편하다.

 

이는 이진수로 숫자를 표기하는 컴퓨터의 방식 때문인데,

먼저 나온 char의 경우처럼, 컴퓨터는 맨 앞자리에 값이 있는걸 가장 작은 음수로 인식한다.

예를 들어, char의 경우 0000 0000 의 공간에 1000 0000 은 -128을 의미하기에 0111 1111의 최대값에

0000 0001을 더하면 1000 0000이 되어 127+1 = -128이 되는 것이다.

 

* 사실 공간복잡도의 영역이라기보다 공간의 영역을 다루는 강의같다.

 

이 개념은 코딩을 하다보면 잊고 왜 원하던대로 되지 않지? 하는 순간이 종종 있다.

값에 대한게 사람은 컴퓨터처럼 바로 연산이 되는게 아니라

연산을 하다보니 값을 초과하는 경우가 있을 수 있는데 이때는 타입을 잘 확인해서 변경하고,

한번쯤 헤매보면 아 혹시 이건가 하는 기억이 날때가 있다.

그 순간이 빨리오길 바랄뿐..

( 물론 고수분들은 다르시겠지만 ) 

 

 

이러한 수를 변수에 저장하는 것이 실수의 범위로가면 직관적이지 않은 상황들이 더 크게 발생한다.

컴퓨터는 이진법으로 수를 계산하기때문에 0.5는 2^(-1)이다.

그렇다면 0.1은 어떻게 될까?

 

2^(-1) = 0.5

2^(-2) = 0.25

2^(-3) = 0.125

2^(-4) = 0.0625

2^(-5) = 0.03125

요런식으로 값들을 구해 계산해보면 0.00011... (2) 로 무한소수가 된다.

이말은 무한한 길이의 수로 표현이 된다는 거고, 아무리 큰 크기를 가진 타입에 이 수를 넣는다고해도

넘쳐서 담기지 않는 값이 생기게 될 거고, 정확한 0.1이 표현되지 않기때문에

0.1+0.1+0.1 = 0.3 이 false가 나온다고 한다.

 

테스트해보니 좀 더 직관적이다. a+a+a는 무한소수를 제한된 크기의 변수에 담다보니 소숫점끝에 숫자가 더 붙어있다.

실수형을 다루게될 때는 오차가 필연적으로 발생한다는 것을 염두에 두어야한다.

또한 실수형은 등호로 값을 비교하기보다 매우 작은 값의 차이를 보인다면 같다고 처리를 하는 방식이 필요하다. 

 

이때 사용되는 것이 정밀도 인데, c언어 기준은 원문을 참조하시기 바란다.

자바는 float은 7자리, double은 15~16자리까지 정밀도를 갖는다.

이는 float는 참값이 1일때, 1-(10^(-7))에서 1+(10^(-7)) 사이의 값을 갖는다는 뜻이다.

즉 비교하려는 값의 차이가 2*10^(-7) 이내라면 같은 값을 의미한다. 

 

 

 

======================================================================

아래는 좀 더 깊은 내용이다.

 

1 byte는 8 bit이니까 char 자료형의 값은 8개의 2진수가 들어간다. ( c언어 기준, 자바는 byte 타입 )

 

( 2진수 0번째, 2진수 1번째, 2진수 2번째... 2진수 6번째 )

20, 21, 22, ··· 26을 나타내는 칸인데, unsigned char에서는 제일 왼쪽이 자연스럽게 27이지만 char에서는 제일 왼쪽이 독특하게 -27입니다. 왜 이렇게 두는지는 전공생이시라면 논리회로 과목에서 배웠을 것입니다. 이 부분이 잘 이해가 안가면 2's complement라는 개념을 찾아보셔도 되고, 굳이 이해를 하지 않고 넘어가셔도 상관은 없습니다.

 

라고 하셔서, 2의 보수 ( 2's complement )를 찾아봤다.

필자는 java를 주 언어로 사용하는데 해당 블로그의 저자는 c언어 기준으로 작성하였다.

크기도 자바의 문자체계와 c언어의 문자체계의 차이로 다르다. ( java : 2byte, c : 1byte )

이러한 차이는 c은 cpu의 비트수와 연관되어 ( cpu는 현재 주로 8비트, 32비트 사용 )결정되었고,

자바는 cpu와 무관하기 때문에 변수에 따라 비트수가 결정되어 있다.

이러한 점은 예시로 든 char일 뿐이니 넘어가고

 

우선 2의 보수는 

 

어떤 수를 커다란 2의 제곱수에서 빼서 얻은 이진수이다. 2의 보수는 대부분의 산술연산에서 원래 숫자의 음수처럼 취급된다.

 

이라고 한다. 오버플로우가 생각나지만 다르다.

 

  . 00000011 (+3  - 8자리)
    . 11111100 (3의 1의 보수)
   +) 00000001 (1 더하기)
    -----------
      11111101 (-3)

( 출처 : https://ko.wikipedia.org/wiki/2%EC%9D%98_%EB%B3%B4%EC%88%98#%EC%BB%B4%ED%93%A8%ED%84%B0%EC%97%90%EC%84%9C%EC%9D%98_2%EC%9D%98_%EB%B3%B4%EC%88%98 )

 

이런식의 2의 보수를 이용해 음수를 표기하는 방식을 취한다고 한다.