[알고리즘] 알고리즘의 성능 평가 | 점근식 표기법 | 순환

 

성능 분석 : 프로그램을 실행하는데 필요한 시간과 공간의 추정

성능 측정 : 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정

 

 

============================================================================================

 

성능 분석

공간 복잡도 : 알고리즘을 실행시켜 완료하는데 필요한 총 저장 공간(고정 공간 + 가변 공간)

시간 복잡도 : 알고리즘을 실행시켜 완료하는데 걸리는 시간(컴파일 시간 + 실행 시간)

점근식 표기법(Asymptotic notation)

• Big-Oh (O) : f, g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a, b가 존재하고, 모든 n >= b에 대해 f(n) ≤ a · g(n) 이면, f(n) = O(g(n))
• Big-Omega (Ω) : f, g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a, b가 존재하고, 모든 n >= b에 대해 f(n) >= a ·g(n) 이면, f(n) = Ω(g(n))
• Big-Theta (Θ) : ➢ f, g가 양의 정수를 갖는 함수일 때,
  세 양의 상수 a, b, c가 존재하고, 모든 n >= c에 대해 a · g(n) ≤ f(n) ≤ b · g(n) 이면, f(n) = Θ(g(n))

연산 그룹

• 상수시간 : O(1)
• 로그시간 : O(logn)
• 선형시간 : O(n)
• n로그시간 : O(nlogn)
• 평방시간 : O(n^2)
• 입방시간 : O(n^3)
• 지수시간 : O(^2n)
• 계승시간 : O(n!)

연산 시간의 순서

• O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

O(n^k) : polynomial time(다항식 시간)

순환 (recursion)

• 정의하려는 그 개념 자체를 정의 속에 포함
• 종류
  • 직접 순환 : 함수가 직접 자신을 호출
  • 간접 순환 : 다른 제 3의 함수를 호출하고 그 함수가 다시 자신을 호출
• 순환 방식의 적용
  • 분할 정복(divide and conquer)의 특성을 가진 문제에 적합
  • 어떤 복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 분할하여 해결하려는 방법
  • 이 작고 간단한 문제는 원래의 문제와 그 성질이 같기 때문에 푸는 방법도 동일

순환 알고리즘과 점화식

점화 관계 : 하나의 값이 자신을 포함한 수식으로 표현되는 것
점화식 : 점화 관계인 식
점화식을 푼다 : 점화식에 대한 폐쇄형 구하는 것