이 영역을 누르면 첫 페이지로 이동
컴퓨터와 수학, 몽상 조금 블로그의 첫 페이지로 이동

컴퓨터와 수학, 몽상 조금

페이지 맨 위로 올라가기

컴퓨터와 수학, 몽상 조금

컴퓨터공학, 딥러닝, 수학 등을 다룹니다.

15. 적분의 상한과 하한(Lower/Upper Bound of Integration)

  • 2020.12.06 21:16
  • 학부 수업/이산수학
반응형

함수 $f$를 다음과 같이 정의해보자.

$$f(i) = \sqrt{i}$$

$f$는 양의 방향으로 증가하는 함수positive increasing function이다.

이런 함수에 대해, 아래가 성립한다.

$$\sum_{i=1}^nf(i) \geq f(1) + \int_1^n f(x) dx $$
$$\sum_{i=1}^nf(i) \leq f(n) + \int_1^n f(x) dx$$

이는 $\sum_{i=1}^n f(i)$의 상한Upper Bound과 하한Lower Bound을 나타낸다.

우리가 알고자 하는 것은 $\sum_{i=1}^n \sqrt{i}$이다.

$$ \begin{align*} \int_1^n\sqrt{x} dx &= [\frac{2}{3}x^{\frac{3}{2}}|^n_1\\
&= \frac{2}{3}(n^{\frac{3}{2}}-1) \end{align*}$$

이므로, 우리가 찾는 값의 상한과 하한은 아래와 같다.

$$f(1)+\frac{2}{3}(n^{\frac{3}{2}}-1) \leq \sum_{i=1}^n\sqrt{i} \leq f(n) + \frac{2}{3}(n^{\frac{3}{2}}-1) $$

$$\frac{2}{3}n^{\frac{3}{2}} + \frac{1}{3} \leq \sum_{i=1}^n \sqrt{i} \leq \frac{2}{3}n^{\frac{3}{2}} + \sqrt{n} - \frac{2}{3} $$

위 식을 변형하면 아래와 같이 나타낼 수 있다.

$$ \frac{1}{3} \leq \delta (n) \leq \sqrt{n} - \frac{2}{3} $$

이제 $\sum_{i=1}^n = \frac{2}{3} n^{\frac{3}{2}} + \delta(n)$로 나타낼 수 있다. $\delta$는 에러항이라 부른다. 에러항을 무시할 수 있음Ignorable을 아래와 같이 표현할 수 있다.

$$\sum_{i=1}^n \sqrt{i} \sim \frac{2}{3} n^{\frac{3}{2}} $$

$\sim$ 기호를 틸드tilde라고 하는데, 아래와 같이 정의된다.

$$ f(x) \sim g(x)\\
\lim_{x\rightarrow \infty} \frac{f(x)}{g(x)} = 1 $$

감소하는 함수

$$ \sum^n_{i=1}\frac{1}{\sqrt{i}}$$

위와 같이 감소하는 함수에서도 같은 방법으로 상한과 하한을 구할 수 있다.

$$f(n) + \int^n_1 f(x)dx \leq \sum_{i=1}^n f(x) \leq f(1) + \int_1^n f(x)dx $$

 

 

 

반응형

'학부 수업 > 이산수학' 카테고리의 다른 글

16. 점근법 표현들 (Asymptotic Notations)  (0) 2020.12.06
14. 관계와 부분 순서 (Relations and Partial Orders)  (0) 2020.12.06
13. 그래프 이론과 오일러 순회, 해밀턴 경로 (Euler Tour, Hamiltonian Path)  (0) 2020.12.06
12. 통신 네트워크 (Communication Networks)  (0) 2020.12.06
11. 그래프 이론과 신장 트리 (Spanning Tree)  (1) 2020.12.05

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 16. 점근법 표현들 (Asymptotic Notations)

    16. 점근법 표현들 (Asymptotic Notations)

    2020.12.06
  • 14. 관계와 부분 순서 (Relations and Partial Orders)

    14. 관계와 부분 순서 (Relations and Partial Orders)

    2020.12.06
  • 13. 그래프 이론과 오일러 순회, 해밀턴 경로 (Euler Tour, Hamiltonian Path)

    13. 그래프 이론과 오일러 순회, 해밀턴 경로 (Euler Tour, Hamiltonian Path)

    2020.12.06
  • 12. 통신 네트워크 (Communication Networks)

    12. 통신 네트워크 (Communication Networks)

    2020.12.06
다른 글 더 둘러보기

정보

컴퓨터와 수학, 몽상 조금 블로그의 첫 페이지로 이동

컴퓨터와 수학, 몽상 조금

  • 컴퓨터와 수학, 몽상 조금의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 방명록

카테고리

  • 분류 전체보기 (276)
    • Tech Trend (3)
    • Deep Learning (77)
      • 공부 노트 (21)
      • 논문 리뷰 (44)
      • 논문 스키밍 (1)
      • 영상처리 (11)
    • Engineering (3)
      • Tips (2)
      • Experiences (1)
    • Blog (42)
      • 회고 & 계획 (16)
      • 내 이야기 (8)
      • 리뷰 (3)
      • 군대에 간 공돌이 (9)
      • ML엔지니어 취업 도전기 (1)
      • 여행 (4)
    • 학부 수업 (141)
      • 머신러닝 (16)
      • C프로그래밍 (8)
      • 자료구조 (11)
      • 알고리즘 (17)
      • 디지털시스템 (25)
      • 컴퓨터구조 (11)
      • 확률과 통계 (21)
      • 선형대수학 (14)
      • 이산수학 (18)
      • 데이터시각화 (0)
    • 강의 (9)
      • 딥러닝 기초 (7)
      • Python (2)

공지사항

인기 글

정보

백지오의 컴퓨터와 수학, 몽상 조금

컴퓨터와 수학, 몽상 조금

백지오

블로그 구독하기

  • 구독하기
  • RSS 피드

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
반응형

나의 외부 링크

  • profile
  • github
  • linkedin

방문자

  • 전체 방문자
  • 오늘
  • 어제
Powered by Tistory / Kakao. © 백지오. Designed by Fraccino.

티스토리툴바