알고리즘 문제 해결 전략 1 - 시간복잡도

 

 

 본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다.

목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. 

 

- 개관

- 반복문

- 선형 시간 알고리즘(이동평균)

 

 

4.11 개관

 시간과 공간은 반비례적인 관계이다. 알고리즘은 속도가 빠른것이 중요하다.

 

4.12 반복문

 알고리즘의 수행시간을 지배하는 것은 바로 반복문이다.

 

4.2 선형시간 알고리즘(이동평균)

 말이 어렵다. 단순히 다음과 같이 설명할수있다.

이 간단한걸 뭐그리 복잡하게 설명해놓는 사람들이 많은지 모르겠다 ㅡㅡ

M이 3일경우라면 위와같이 앞의 3개의 평균이다. 최소 3개는 있어야 평균을 구할수있으니 3번째부터 시작하는것이다.

책에 나온것을 요약해서 설명하자면

본래 코드 4.3 에 구현된것은 무식하게 계산한거지만 이미계산된것은 제외하고 추가만해서 평균값을 구하는 코드인 4.4로 수정해서 하면

코드 시간 복잡도가 N으로 줄어든다는것이다.

이처럼 시간과 정비례하는 알고리즘을 선형 시간 알고리즘이라고 한다.

 

4.3 선형 이하 시간 알고리즘 

- 이진탐색

이진탐색은 선형 이하 시간 알고리즘중에 하나이다. 간단한 아이디어와 달리 이진탐색 알고리즘은 구현하기가 매우 까다로워서 버그 없는 코드를 작성한 사람이 채 절반도 되지 않았다는 일화가 있음

 

4.4 지수 시간 알고리즘

- 다항 시간 알고리즘

 N의 거듭제곱의 형태로 이루어진 다항식이라고 부름

 

- 모든 답 평가하기

 재귀호출 사용하여서 하나하나 따져보기

 

- 지수시간 알고리즘

 N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘이다. 지수시간은 시간이 굉장히 오래걸린다. 이러한 문제들이 아주 많아서 전산학에서 효율적으로 해결할 수 있는 문제와 효율적으로 해결하는 방법을 아직 찾아내지 못한 문제의 경계 역할을 하고 있음

다항시간 알고리즘 -> 쉬운 알고리즘

지수시간 알고리즘 -> 어려운문제

 

- 소인수 분해의 수행 시간

 어떤 수 N의 약수들중 소수들을 소인수라고하며 N을 소수들로만 표현하는것을 소인수분해

입력의 크기를 입력이 차지하는 비트 수로 정의하면 지수시간이 걸린다고 말할수 있음

 

4.5 시간 복잡도

~200211