[알고리즘 기초] 알고리즘의 복잡도

 

알고리즘이 주어진 경우에는 알고리즘의 연산 수행 횟수를 파악해 함수로 표현할 수 있어야 합니다. 연산 수행 횟수란 선언 및 초기화 문이난 조건문, 반복문을 제외한 순수한 실행문으로, 산술연산 뿐만 아니라 출력문이나 return문이 수행되는 횟수를 포함합니다. 

 

특히 산술연산은 하나의 식 내에 포함된 연산자의 수만큼 실행된다고 가정하고 연산횟수를 파악합니다. 예를 들어

a= (a+b) / c + 1 의 경우 연산 과정이 다음과 같습니다.

 

x = a + b,                     y = x / c         ,            a = y + 1

 

그러므로  a = (a+b) / c + 1의 연산 실행 횟수는 3이 됩니다.