[계산이론](26)[time complexity]

time complexity

풀 수 있는가? (decidable / undecidable)
-> 그럼 '실제로' 풀 수 있는가? (P / NP)

 

단순히 풀 수 있다 없다를 넘어
현실적으로 시간, 자원 등을 소모하여 풀 수 있겠는가?

time complexity theory

• 시간 복잡도를 측정하는 방법
  BIG-O 표기법
  (자료구조 1 참고...)
  -> 이때 기준을 single deterministic TM으로 삼는다
• polynominaly diff VS exponetialy diff
  만약 다항식 형태면 polynominal하게 다르다고 하고
  equivalent하다고 한다.

 

Single-tape TM VS Multi-tape TM

STM의 시간 복잡도가 O(t(n))이라 해보자.

이떄 MTM은 과연 얼마나 걸릴까?

 

MTM -> STM이 가능함은 이미 증명했다.
따라서 이떄 STM으로 만든 MTM을 S(MTM)이라 하자.

그럼 S(MTM)이 실제 MTM의 동작을 따라하기 위해선 얼마나 연산을 해야할까?

 

MTM: 1 step에 N개의 head로 N개의 정보를 읽어 연산 가능
S(MTM): MTM의 동작을 따라하기 위해 N step이 필요하다.
    현재 .을 찍은 head위치가 어디 있는지 #~#사이를 훑어야 함
        최대 tape 길이 전체를 스캔해야 할 수도...
        이떄, tape의 길이는 실행시간 t(n)에 비례함
(단순하게 전체 tape를 스캔하고 1칸씩 shift하는 TM을 생각해보셈)

	MTM	S(MTM)
1 step	1	k (= tape의 길이)
2 step	1	k * 2
...	...	...
t(n) step	1	k * t(n)
total time	t(n)	kt(n^2)

따라서 MTM은 O(t(n^2))정도의 시간복잡도를 가진다
    polynominal하게 차이가 나므로, equivalent하다 하자

 

Deterministic TM VS Nondeterministic TM

DTM의 시간 복잡도가 O(t(n))이라 해보자.

이떄 NTM은 과연 얼마나 걸릴까?

 

NTM -> DTM이 가능함은 이미 증명했다.
따라서 이떄 DTM으로 만든 NTM을 D(NTM)이라 하자.
그럼 D(NTM)이 실제 NTM의 동작을 따라하기 위해선 얼마나 연산을 해야할까?

 

NTM: 1 step에 그 state에서 할 수 있는 모든 경우를 다 볼 수 있음
D(NTM): NTM의 동작을 따라하기 위해 b^N step이 필요하다
    모든 분기를 하나하나 연산해야 함
        모든 state에서 최대 분기 수가 b라고 할때,
        최악일 때는 그 분기 전부를 봐야 함

	NTM	D(NTM)
1 step	1	b (= 최대 분기 수)
2 step	1	b^2
...	...	...
t(n) step	1	b^t(n)
total time	t(n)	$t(n)b^{t(n)}$ <- 가장 지배적인 항에 대해서만 계산

따라서 NTM은 O($2^{t(n)}$)정도의 시간복잡도를 가진다
    polynominal하지 않다...