공간(space)과 시간복잡도(time) 사이 관계

1. problem space

 

어떤 문제가 정의되는 공간

 

문제에서 이 공간 밖에서는 어떠한 것도 생각하지 않겠다

 

 

1-1) example

 

어떤 game의 finite state space

 

현재 상태에서 어떤 변화가 주어지면 다음 상태로 이동하는 space

 

동그라미 2개 있는 곳이 final state

 

game의 player는 아래와 같이 정의된 problem space내의 상태 변화만 가능하다

 

 

input으로 플레이어?가 주어지면 patrol을 하면서 순찰을 함

 

player approach로 어떤 player가 접근하면? attack 상태로 변화

 

attack 상태에서 player가 도망가면? 다시 patrol 상태로 변화

 

patrol중에 체력이 없어 no health면? deceased로 사망 상태로 변화

 

 

1-2) fibonacci

 

n번째 피보나치 수열의 값을 구하고자 할 때 n-1, n-2를 찾고

 

n-1에서 n-2,n-3을 찾고 n-2에서 n-3,n-4를 찾고

 

마지막에 1,2를 찾으면 다시 위로 합해나가서 최종적으로 n번째 값을 구함

 

 

 

갑자기 이 공간 밖의 n+1이나 n+2를 찾지는 않는다

 

 

2. solution space

 

feasible region, search space라고도 불린다.

 

problem space에서 정의되는 problem의 constraint를 모두 만족시키는 ‘point’의 집합

 

이름이 정답의 집합이라는 인상을 주는데 단순히 정답의 집합이 아니라 정답이 될 수 있는(정답이 아니더라도 가능성은 있는) 후보들의 집합

 

 

2-1) example

 

"minimize $x^{2} + y^{4}$ subject to 1≤x≤10, 5≤y≤12"

 

제약조건 1≤x≤10, 5≤y≤12 을 모두 만족시키는 (x,y)의 집합이 solution space다.

 

$x^{2} + y^{4}$을 2차원에 쉽게 표현하기는 어려우니 $y^{2}=k$라고 하여 (x,k)의 집합으로 나타내면…

 

optimal point가 solution space가 아니라는 것을 아는 것이 중요할듯

 

>>> solution space가 단순히 정답의 집합이 아니라 정답의 가능성이 있는 후보들의 집합

 

>>> solution space의 원소인것은 맞지만 solution space라는 인상때문에

optimal point가 유일한 solution space로 착각하지 마라 이 말인듯

 

 

 

빨간색 실선이여야하는데 점선으로 잘못 그렸네..?

 

빨간색 사각형 부분이 제약조건을 모두 만족시키는 solution space

 

파란색 point가 objective를 minimize 시키는 optimal point

 

 

2-2) 한붓그리기

 

주어진 node에서 모든 node를 최소 비용으로 한번에 지나가는 경로를 찾는 문제

 

가능한 한붓그리기 경로들이 제약조건을 만족시키는 것이므로 solution space에 속할 것

 

이 중에서 최소 비용을 가지는 optimal point를 찾는 것이 optimization problem

 

 

 

빨간색 box안에 있는 6개의 경로들이 한붓그리기를 만족하니 solution space

 

빨간색 box 밖에 있는 것들은 5개 node를 지나지 못하니 제약조건을 만족시키지 못하므로 solution space가 아니다

 

solution space안에 optimal point가 존재한다

 

 

2-3) 팩맨, 스타크래프트, 바둑

 

각각의 게임은 그 게임 자체로 problem space이고 갑자기 다른 게임이 되거나 하지 않는다.

 

게임 1판하는 것이 problem solving이랑 마찬가지

 

initial state에서 게임을 하면서 terminal state로 가는 중 일어나는 무수한 상황들이 solution space에 속함

 

 

 

팩맨 게임이 스타크래프트가 된다거나 스타크래프트가 바둑이 된다거나 하지는 않는다

 

게임을 하면서 일어나는 모든 상황들이 게임의 제약조건을 만족하는 상황들이므로 solution space에 속한다

 

 

2-4) bubble sort

 

bubble sort로 최종 output을 얻기까지 모든 list들이 solution space에 속한다

 

 

 

3. time complexity

 

주어진 input size에 대해 얼마나 계산량이 증가하는 알고리즘인지 나타내는 측도

 

수학적으로 f(x)  = O(g(x))는 " 모든 x ≥ $x_{0}$에 대하여 f(x) ≤ cg(x)을 만족시키는 c>0 , $x_{0}$가 존재한다."

 

 

3-1) P=NP vs. P ≠ NP

 

P는 다항시간 이내에 해결가능한 문제들의 집합을 말한다.

 

NP는 다항시간 이내에 답의 존재 유무를 알 수 있는 문제들의 집합이다.

 

NP의 문제가 다항시간에 해결할 수 있는지 없는지는 아무도 증명하지 못했다.

 

모든 NP 문제를 다항시간 내에 어떤 문제 A로 바꿀 수 있으면 A를 NP-hard라고 부름

 

NP-hard는 이름에서 알 수 있듯이 NP보다 어려운 문제이고 NP-hard를 해결할 수 있으면 NP를 해결할 수 있음

 

NP-complete는 NP-hard이면서 NP인 문제를 말함

 

정의상 P는 NP의 부분집합인데 아직까지도 증명하지 못한 것은 NP가 P의 부분집합인지이다.

 

만약 P=NP이면 모든 NP인 문제는 방법만 찾으면 P문제로 해결할 수 있다는 의미이고

 

P ≠ NP이면 NP인 문제를 굳이 P로 바꾸는 방법을 찾으려고 할 필요가 없다는 의미를 가진다.

 

P 문제들은 컴퓨터로 돌리면 그냥 쉽게 나오는 문제

 

NP 문제들은 컴퓨터가 아무리 돌아도 답인지 아닌지 찾아볼게 너무 많아서 쉽게 나오지 않는 문제

 

NP 문제부터 머신러닝이 효과를 발휘한다고 할 수 있는데 머신러닝 모델은 NP에 대해서 다 찾아보지 않고 candidate만 몇개 찾아주고 답이라고 쓰라함

 

 

문제 class의 종류를 계층적으로 표현

 

계층이 올라갈수록 해결하는데 오랜 시간이 걸려 어려워짐. 심지어 안풀릴수도 있음

 

알고리즘이라는 것은 문제를 돌려서 유한시간에 해결이 가능한 것이라고 했고

 

그 이상의 class는 해결이 안되니까?(될수도 있지만 너무나 오랜시간이 걸려서) 알고리즘이 아니라고 하는 부분이 눈에 띔

 

가장 간단한 문제로 regular language는 전에도 나왔지만 어떤 문자열의 집합에서 정규표현식으로 원하는 문자열을 찾는 문제

 

이것이 발전하여 튜링머신부터 여러 문제들이 되었다고 언급함

 

 

4. time-memory trade off

 

""알고리즘에서 문제를 해결하거나 연산을 위해서 메모리 공간을 더 사용하는 대신에 해결 시간을 줄일 수있다.

 

반대로 메모리 공간을 조금만 사용하면 문제 해결 시간이 오래 걸릴 수 있다.""

 

메모리 공간을 덜 쓰면 주어진 공간안에 문제 해결에 필요한 데이터가 없을 가능성이 높아서 다른데서 데이터를 또 찾아오는 시간이 더 걸린다

 

data compression 관점에서 data가 uncompressed되어 공간을 많이 차지한다면 사용한 메모리 공간은 많지만 data 접근하는 시간이 빨라 시간을 아낄 수 있다.

 

반대로 data를 compress하면 메모리 공간을 아낄 수 있겠지만 compress하는데 걸리는 시간이 더 소요되니까<추가로 데이터가 없을 가능성이 높아 다른 곳에서 찾아와야하는 데 걸리는 시간도 소요> 문제 해결에 더 오랜시간이 걸릴 수 있다