[CLRS] [4-3] The substitution method

2024. 9. 6. 14:18· CS Study/CLRS (자료구조 | 알고리즘)
목차
  1. 1. Introduction
  2. 2. Substitution Method
  3. 3. reference

1. Introduction

- 분할 정복(DIvide & conquer)알고리즘의 시간복잡도를 구할 수 있는 네가지 방법중
가장 일반적인 "substitution method"에 대해 알아보자.

- "substitution method"은 두가지 단계로 구성되어 있다.

1)  해당 알고리즘의 시간복잡도를 n에 대한 함수로 가정

2)  수학적 귀납법을 사용하여 그 해가 성립하는지 증명하고, 해당 상수를 찾아낸다.

 

2. Substitution Method

- Substitution Method을 사용하면 재귀 알고리즘에서 상한 또는 하한을 설정가능하다(Big-O , Big-Omega)

- 해당 방법을 이용하기 위해선 Big-Theta를 증명하려고 하기보단, 

- Big-O를 먼저 증명하고 그 다음에 Big-Omega를 증명한후 그 두개를 합쳐서 Big-Theta를 유도하는게 좋다.

- 다음 예시를 통해서, 해당 재귀 알고리즘의 Big-O를 구해보자.

ex)

- 우선 T(n)이 O(nlog2(n) + n)라고 가정하는 것이다. (이때의 가정은 정말 직관으로 예측해야한다.)

- 그 후 귀납에 의한 증명을 다음과 같이 하면 된다.

 

i) n = 1, 성립함을 보이자.

1 * log2(1) + 1 = 0 + 1 = O(1)

 

ii) n보다 작은 임의의 k에 대해 성립한다고 가정해보자.

k * log2(k) + k = O(K) 라고 할때,

 

iii) k/2 일때도 성립함을 보이자.

- T(n) = nlog2(n) + n = O(nlogn) 임을 알 수 있다.

- 즉 Substitution method는 가정을 제대로 설계하지 않으면 증명이 불가능하다는 단점이 존재한다.

 

3. reference

https://velog.io/@dandyoung/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%9D%98-%EA%B3%84%EC%82%B0%EB%B3%B5%EC%9E%A1%EB%8F%84

'CS Study > CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글

[CLRS] [4-5] The master method(마스터 정리)  (0) 2024.09.09
[CLRS] [4-4] Recursion Tree Method(재귀 트리)  (0) 2024.09.06
[CLRS] [4-2] Strassen’s algorithm  (4) 2024.09.06
[CLRS] [4-1] Multiplying square matrices(행렬 곱)  (1) 2024.09.05
[CLRS] [3-1] 시간 복잡도 (big-O, big-Ω, big-θ)  (0) 2024.09.04
  1. 1. Introduction
  2. 2. Substitution Method
  3. 3. reference
'CS Study/CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글
  • [CLRS] [4-5] The master method(마스터 정리)
  • [CLRS] [4-4] Recursion Tree Method(재귀 트리)
  • [CLRS] [4-2] Strassen’s algorithm
  • [CLRS] [4-1] Multiplying square matrices(행렬 곱)
23학번이수현
23학번이수현
23학번이수현
밑바닥부터 시작하는 AI보안전문가
23학번이수현
전체
오늘
어제
  • 분류 전체보기 (243)
    • Statistic Study (47)
      • Mathematical Statistics(수리통.. (47)
    • Mathematics Study (15)
      • Linear Algebra (선형대수학) (15)
    • CS Study (74)
      • CLRS (자료구조 | 알고리즘) (49)
      • Database(DB) (11)
      • C++ (11)
      • 컴퓨터 구조 (2)
      • MongoDB (1)
    • DS Study (56)
      • CS 229(Machine Learning) (19)
      • CS 224n(NLP) (5)
      • Web Scraping (7)
      • R4DS(R언어) (20)
      • 밑바닥부터 시작하는 딥러닝 1 (5)
    • Hacking Study (0)
      • Web Hacking (0)
    • 코딩테스트 (5)
      • 백준-Python (5)
    • Paper Review(논문 리뷰) (43)
      • Deep Learning (16)
      • TCGA 관련 논문 (4)
      • Computer Vision (18)
      • NLP (5)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 알고리즘
  • Algorithms
  • web scraping
  • R언어
  • db
  • Data Structure
  • Introduction to Algorithms
  • R4DS
  • graph
  • LSTM
  • NLP
  • introduction to algoritmhs
  • Linear Algebra
  • 파이썬
  • clrs
  • 자료구조
  • Machine Learning
  • 정렬
  • 데이터분석
  • deep learning
  • 백준
  • 시간복잡도
  • cs 224n
  • 수리통계학
  • cs229
  • 딥러닝
  • C++
  • 선형대수학
  • 논문 리뷰
  • AI

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
23학번이수현
[CLRS] [4-3] The substitution method
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.