23/99 알고리즘 ? 시간복잡도 ?

내일 cs 스터디 시간에 발표할 내용 정리

 

시간 복잡도란 ?

알고리즘의 효율성을 판단하기 위한 지표로서, 프로그램 수행에 걸리는 절대적 시간이 아닌, 

알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다.

연산에는 산술, 대입, 비교, 이동이 있다.

상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수

지수 알고리즘

n^2 의 형태로 알고리즘 풀이의 마지노선 느낌?

시간 계산량이 지수 함수의 차수로 되어 있는 알고리즘

 다항식 알고리즘보다도 압도적으로 시간 계산량이 많기 때문에 입력 데이터량이 작을 때만 가능하다.

보통 지수 알고리즘은 머리를 조금 쓰면 로그 알고리즘으로 변환하여 풀 수 있다고 함.

 

P vs NP

 

• 만약 다항식 시간(polynomial time) 내 결정적 알고리즘(a deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional problem) x 가 있다면  x 는 P의 클래스 안에 있다. 
• 만약 다항식 시간(polynomial time) 내 비결정적 알고리즘(a non-deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional problem) x 가 있다면  x는 NP의 클래스 안에 있다.

다항식 시간(Polynomial time)

• 단순히 말해서 다룰 수 있는 시간 내에 해결가능하다는 의미입니다. 이에 반대되는 의미는 지수시간(exponential time)으로 시간내 해결 불가능한 다루기 힘든 경우

결정적 알고리즘(a deterministic algorithm) 

• 특정한 값을 입력하면 그에 따라 정해진 값이 나오는 것.

비결정적 알고리즘(a non-deterministic algorithm)

• 동일한 값을 입력해도 다른 결과를 출력할 수 있다.