4장: 알고리즘 분석 - 2 (114p ~ 126p)

<수행 시간 어림짐작하기>

1. 주먹구구 법칙

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

• 그래도 예측한 수행 횟수가 기준의 10%이하인 경우와 기준의 10배를 넘는 경우에만 이 법칙을 적용하는 것이 좋다. (어림짐작이기 때문이다.)

 

2. 주먹구구 법칙은 주먹구구일 뿐이다.

• 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: O표기법으로 시간 복잡도를 표현할 때 상수나 최고차항 이외의 항들을 모두 지워버리므로 실제 프로그램이 수행하는 반복문의 수는 이 계산의 다섯 배일 수도 있고, 10분의 1배일 수도 있다.
• 반복문의 내부가 복잡한 경우: 실수 계산이나 파일 입출력과 같은 함수들이 많이 있는 경우 시간이 더 오래 걸릴 수가 있고, 반대로 단순하면 더 짧게 걸린다.
• 메모리 사용 패턴이 복잡한 경우: 현대 CPU는 캐시로 자료를 가져오는데 이때 인접한 자료도 같이 가져와서 인접한 자료들을 연속해서 사용하는 프로그램은 수행 속도가 빨라지게 된다.
• 언어와 컴파일러의 차이: 최적화 옵션이 꺼져 있거나, 더 느린 언어를 사용하면 수행 시간이 더 걸린다.
• 구형 컴퓨터를 이용하는 경우: 주먹구구의 법칙은 4~5년 전 사이 컴퓨터를 기준으로 한다.

 

3. 계산 복잡도 클래스: P, NP, NP-완비

• 계산 복잡도 이론에서 다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 한다.
• NP는 non-polymial이 아니다. 즉 다항 시간 알고리즘이 존재하지 않는 문제들의 집합이 아닌 것이다.
• 계산 복잡도에서 A가 B보다 어려운 문제임을 알 수 있는 방법은 B의 입력을 적절히 변형해 A의 입력으로 바꾸는 환산 알고리즘을 A와 결합해 B를 푸는 알고리즘을 만들 수 있고 이때 환산 알고리즘이 빠르다면 A가 B이상으로 어려운 문제가 되는 것이다. ex) 최솟값 문제는 정렬 문제 해결 과정에서 간단히 해결할 수 있으므로 정렬 문제는 최솟값 문제보다 어려운 문제이다.
• NP 문제, NP 난해 문제: SAT 문제(satisfiability problem)보다 어려운 문제를 NP-난해 문제라고 하며 이때 NP인 문제를 NP-완비(NP-Complete) 문제라고 한다. NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미한다.
•  NP=P?: 어려운 문제를 풀다가 어떤 변환을 거치면 이 문제를 이용해 NP-난해 또는 NP-완비 문제를 풀 수 있음을 깨달았다면 이는 다항 시간에 푸는 것은 불가능하므로 근사해를 찾는 등 다른 방향으로 돌아가는 길을 모색해야 한다.

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.