[Automata] Complexity

Complexity

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Complexity

Complexity는 알고리즘이 문제를 풀고 원하는 결과를 산출하는 데 걸리는 시간이 얼마나 되는지를 나타내는 걸 의미한다.

Automata에서는 Polynomial time을 Turing machine으로 결과를 산출할 수 있다.

하지만 Polynomial time의 특성에 따라 방식을 나눠서 부르는데, 오토마타에서는 Class P와 Class NP, Class NP complete 등으로 구분하여 부른다.

Automata에서 Class P라고 불리는 Complexity의 경우에는 Polynomial time이며 Deterministric turing machine으로 문제 해결이 가능하다.

여기서 말하는 Polynomial time이나 Non-polynomial time은 input size를 의미한다.

Class NP도 마찬가지로 Polynomial time의 문제를 해결하는데 사용하지만 Non-deterministic turing machine을 사용하는 것이 Class P와 차이점이다.

마지막으로 Class NP complete는 NP 문제를 다루지만 Polynomial time으로 다룰 수 있는 것을 의미한다.

 

우리가 굳이 현재 일상 생활에서 사용하지도 않는 Turing machine 기준으로 나누어진 Complexity, 즉 복잡도에 대해서 배워야 하는 이유는 사실상 효율성 때문이다.

컴퓨터를 사용하는 근본적인 이유는 사람이 할 수 있는 일이지만 컴퓨터를 사용함으로써 정확한 결과를 산출해내며 자동화를 통해 편안함을 얻기 위해서이다.

결과적으로 작업 수행 속도가 빨라질 수록 효율성도 증대되고 컴퓨터를 사용하는 목적이 달성될 수 있다.

이것을 우리는 Time complexity라고 부른다.

각 문제에 따라서 어떤 알고리즘을 사용하느냐에 따라서 산출되는 결과 속도는 매우 다르다.

한 문제를 푸는데 A 알고리즘은 몇백년이 걸릴 수 있고, B라는 알고리즘은 몇 년 안에 문제를 해결할 수도 있다.

이러한 시간의 효율성을 파악하기 위해서 Time complexity를 활용하는 것이다.

Time complexity가 나올 쯤, Cook의 NP complete과 Big O notation도 나오게 되었다.

---