성능 분석 : 프로그램을 실행하는데 필요한 시간과 공간의 추정
성능 측정 : 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정
----------------아래 내용은 모두 성능 분석-----------------------------
공간 복잡도 : 알고리즘을 실행시켜 완료하는데 필요한 총 저장 공간(고정 공간 + 가변 공간)
시간 복잡도 : 알고리즘을 실행시켜 완료하는데 걸리는 시간(컴파일 시간 + 실행 시간)
점근식 표기법(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)의 특성을 가진 문제에 적합
- 어떤 복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 분할하여 해결하려는 방법
- 이 작고 간단한 문제는 원래의 문제와 그 성질이 같기 때문에 푸는 방법도 동일
순환 알고리즘과 점화식
점화 관계 : 하나의 값이 자신을 포함한 수식으로 표현되는 것
점화식 : 점화 관계인 식
점화식을 푼다 : 점화식에 대한 폐쇄형 구하는 것
내가 손으로 해서 이미지 첨부
