Performance

보통 코드의 성능을 측정하는 데 두 가지 요소가 있는데,

Time Complexity:

• Time requirement
• The time it takes to execute

Space Complexity:

• Space requirements
• the memory it needs to execute

하나는 시간이 얼마나 걸리는지, 두 번째로는 얼마나 많은 용량을 차지하는지이다. 이때 용량은 RAM을 말하는 것이다. 여기서 Time Complexity를 어떻게 측정하는지 보자.

• Problem Size
• Basic Algorithm / Actual Processing
• Memory Access Speed
• CPU/processor speed
• the number of processors
• Compiler/Linker optimization

 우선 위의 요소들에 의해 시간이 측정이 되지만, 이는 HW측면이지 프로그래머의 입장에서는 고려해야 할 요소가 아니다. 여기서 고려해야 할 것이 바로 Basic Operation 이다. 어떤 문제를 풀기 위해 필요한 기본 작업을 일컫는데, 이렇게 되면 유사한 유형의 문제들이더라도 Problem Size에 따라 연산이 directly proportional하다고 할 수 있다. 이를 비약적으로 함수로 나타내는 것이 growth-rate function T(n)이라고 한다. 이렇게 함으로써 다른 알고리즘과 비교가 가능하게 되는 것이다. 측정할 때 단순하게 측정하는 것이면, 이런 기본 작업들을 산술 연산 수, 비교 횟수, loop 횟수, 배열 요소를 접근하는 횟수 등을 고려하여 측정할 수 있다.

여기서 growth-rate function에 따라 시간이 얼마가 걸리는지 category를 나눌 수 있는데, 다음과 같다.

• Constant Time 상수 시간
• Linear Time 선형 시간
• Quadratic Time 이차 시간(for 2중 중첩)

 여기서 growth-rate function은 n에 대한 큰 영향을 미치는 term 즉, Dominant term에만 관심을 가지는데, 쉽게 말해 limit를 취했을때, n^3은 n에 무시 될 만한 수준으로 상대적으로 작기 때문에 n^3 만큼의 시간이 필요하다고만 말한다. 그래서 크기 순서대로 나열해본다면, Constant < Log Time < Linear Time < Linear * Log Time < Polynomial Time < Exponential < Factorial 이다. 보통 Polynomial Time 이 걸리는 수준의 문제를 다루기 쉬운 문제, solvable problem 이라고 얘기를 함.

 

Asymptotic Notation

 위에서 Dominant Term 에 대해 시간이 얼마나 걸리는지를 나타내는 표기 방법을 Asymptotic Notation이라고 하는데, 이 방법은 크게 3가지가 있다.

• Big O notation - 점근적 상한
• Big Omega notation - 점근적 하한
• Big Theta notation - 점근적 동일

  예제를 보면 쉬운데 O(n^2)이 걸린다는 것은 기껏해야 n^2이 걸린다 라는 의미로 쓰이며 이 말은 3n, nlogn등도 포함이 되는 개념이다. Omega(n^2)은 최소 n^2이 걸린다 등으로 쓰일 수 있다. 이 둘의 교집합을 Big Theta of n^2 이라고 한다.