🔑Algorithm

수학적 귀납법 귀납법은 연역법의 한 분야로, 논리적인 추론을 수행하는 방법 중 하나이다. 증명 과정이 타당하다면 결론 역시 반드시 타당하기 때문에 완전귀납법이라고도 한다. 1. 기초 단계 : 먼저, 귀납법을 적용할 명제나 정리가 초기 조건에서 참인지 확인한다. 즉, 명제의 첫 번째 단계나 가장 작은 값을 가지는 경우를 검토한다. 2. 귀납 단계 : 명제나 정리가 기초 단계에서 참이라고 가정하고, 그 가정 하에서 다음 조건이 참임을 증명한다. 이를 통해 모든 조건에서 명제나 정리가 참임을 보일 수 있다. 1) 가정 단계 : 귀납적 가정을 설정한다. 기초 단계에서의 가정을 귀납 단계에서도 유지하기 위해 가정을 설정한다. 2) 추론 단계 : 가정에 기초하여 다음 조건에서도 명제나 정리가 참임을 추론한다. 이를..

점근표기법 알고리즘의 성능을 표현하는 수학적 표기법이다. 알고리즘의 시간 복잡도(실행시간)나 공간 복잡도를 표현하는 데 사용된다. 알고리즘의 실행시간은 하드웨어나 운영체제 등 여러 영향에 따라 다르게 측정될 수 있다. 실행환경을 동일하게 하는 것은 어렵기 때문에 알고리즘의 효율을 측정하기위해 점근 표기법을 사용한다. 1. 빅 오메가 표기법 최선의 경우 실행시간이나 공간 복잡도의 하한을 나타낸다. 최선의 경우에서 알고리즘의 실행 시간이나 공간 복잡도가 감소하는지를 나타낸다. f(n) = Ω(g(n)) g(n)을 함수 f(n)의 점근적 하한이라고 한다. 즉 f(n)의 복잡도는 최선의 경우라도 g(n)보다 크거나 같다는 의미이다. f(n)≥g(n) g(n)보다 더 좋을 수는 없다. 2. 빅 세타 표기법 알고리..