4..md

description
알고리즘을 풀며 가장 중요한 부분인데 귀찮아서 매번 대충 이정도겠지 하고 푼다

4. 알고리즘의 시간 복잡도 분석

선형 시간 알고리즘(Linear time)

N에 정비례한 알고리즘.

1448: 삼각형 만들기 같은 문제도 사실 N이면 풀 수 있는데 굳이 N^3으로 처 풀겠다고 고집부리다 실패했다.

선형 이하 시간 알고리즘(Sublinear time)

입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘.

지수 시간 알고리즘(Exponential time)

N의 거듭제곱들의 선형 결합으로 이루어진 알고리즘.

이 후의 장에서 지수 알고리즘을 좀 더 효율적으로 다루는 법 가르쳐 준다함.

시간 복잡도(Time complexity)

수행 시간 어림짐작하기

주먹 구구 법칙

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능이 있다.

개꿀팁(내가 이거 맨날 몰라서 대충 품)

• N = 1000 : N^3 하면 10억. 반복문이 단순한거면 가능.
• N = 10000 : N^3이면 1조. N^3은 가능성 없음. N ^2^ 이면 1억이라 아슬하게 가능.
• N = 100000 : N^2 100억이니 NlgN 아니면 가능성 없음.
• O(N^3) 알고리즘 : 입력 2560 까지 1초 가능
• O(N^2) 알고리즘 : 입력 40960 까지 1초 가능
• O(NlgN) 알고리즘 : 입력 2천만까지 1초 가능
• O(N) 알고리즘 : 입력 1억 6천만까지 1초 가능

계산 복잡도 클래스(Complexity class)[?????]

같은 성질을 갖는 문제들을 모아놓은 집합.

결정 문제

답이 YES 아니면 NO로 반환되는 문제를 결정 문제.

P 문제(Polynomial)

결정 문제들 중에 쉽게 풀리는 것을 모아놓은 집합. 다항식 시간 이내에 그 문제의 답을 YES와 NO 중의 하나로 계산해낼 수 있는 알고리즘 있으면 P 문제에 해당.

NP 문제(Non-Polynomial)

결정 문제들 중에서 적어도 검산을 쉽게 할 수 있는 것을 모아 놓은 집합. 문제의 답을 입증하는 힌트가 주어지면 그 힌트를 사용해서 그 문제의 답이 맞다는 것을 다항식 시간 이내에 확인 할 수 있는 문제