1. Algorithm 알고리즘

알고리즘

알고리즘

알고리즘 : 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말한다.

즉, 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다.

컴퓨터 분야에서 알고리즘을 표현하는 방법은 크게 두 가지

• 의사코드(슈도코드, Pseudocode)와 순서도

 

알고리즘의 성능 측정

좋은 알고리즘

• 정확성 : 얼마나 정확하게 동작하는가
• 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
• 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
• 단순성 : 얼마나 단순한가
• 최적성 : 더 이상 개선할 여지없이 최적화되었는가

 

주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능

⇒ 어떤 알고리즘을 사용해야 하는가?

 

알고리즘의 성능 분석 필요

• 많은 문제에서 성능 분석의 기준으로 알고리즘의 작업량을 비교한다.

 

시간 복잡도(Time Complexity)

측정 방법

• 실제 걸리는 시간을 측정
• 실행되는 명령문의 개수를 계산

시간 복잡도 ≓ 빅-오(O) 표기법

 

빅-오 표기법 (Big-Oh Notation)

시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

계수(Coefficient)는 생략하여 표시

 

ex)

O(3n + 2) = O(3n) = O(n)

O(2n² + 10n + 100) = O(n²)

O(4) = O(1)

: 최고차항만 선택, 계수 제거

 

n개의 데이터를 입력 받아 저장한 후 각 데이터에 1씩 증가시킨 후 각 데이터를 화면에 출력하는 알고리즘의 시간 복잡도? → O(n)