[알고리즘] 효율적인 알고리즘

ㅁ 계산량

문제에 맞추어 효율적인 알고리즘을 생각할 때 중요한 것은 계산량

계산량 측정

4중 루프가 n번 돌기 때문에 실행시간은 n 4승 에 비례 합니다.

그리고 n 4승 비례한다는 것은 O(n4스) 이라고 쓰고, 실행시간 [O(n4승)]이라고 씁니다.

- 이것은 런다우 기법(Landau notation) 또는 O-기법이라고 한다.

 

ㅁ 실행시간

- 알고리즘에 따른 계산량 만으로도 프로그램의 속도 차이가 수십배 나는 경우도 있다.

프로그램의 실행시간을 짧게 하기 위해서는 우선 알고리즘 계산량이 중요하다는 뜻.

 

ㅁ

알고리즘에 제한시간 안에 실행 가능한지 판단하기 위해서는 계산량 오더 식에 최대치를 대입

예 : O(n4승)시간 알고리즘 일때 (n<=1000)이라는 제약일 경우, n2승에 n=1000 을 대입하면 1,000,000이 된다.

     이를 통해 다음과 같이 짐작

    실행시간 제한이 1초인 경우

  1,000,000    여유가 있음

  10,000,000  적어도 제한시간 안에는 결과가 아놈

  100,000,000 매우 심플한 처리가 아닌 경우에는 위험

 

* 책(프로그래밍 콘테스트 챌린징) 중에서