[💬] 코드몽키 벗어나기 - 9

2주동안 감기로 죽는줄 알았다.

여튼 어느정도 회복되었으니 이 빌어먹을 시리즈를 다시 시작하기로 함.

아직 몸이 완전한 상태가 아니니 맛만 살짝 보기로

여태까지 요약.

SICP 정독중.

프로그래밍 언어를 이해하기 위해서 가장 기본적인 개념부터 쌓아올리는중.

대충 가장 기본 단위인 프로시져, 프리미티브 데이터, 가장 간단한 추상화를 배웠고

그 다음은 그것들을 이용해서 간단한 프로세스 (linear recursion 등등)을 공부했다.

간단한 프로세스라도 어떻게 구현하냐에 따라 계산에 사용되는 시간과 메모리양이 크게 달라진다는것도 배웠음.

이번 챕터에서는 프로세스에서 사용되는 계산 리소스를 어떻게 표현하는가? 이것을 설명하고 있음.

책에서는 Order of Growth 라고 부르는데, 설명을 요약하면 아래와 같다.

n -> 문제의 크기를 재는 파라메터

R(n) -> 크기 n 의 문제를 풀기위해 필요한 리소스의 양

여기에서 n은 문제에 따라 여러가지 다른 파라메터가 될 수 있음.

예를 들어서 문제에 따라서 몇자리까지 정확하게 제곱근을 구할것인가로 설정한다던가

메트릭스 곱셈에서 메트릭스의 행수 라던가가 n 이 될 수 있고,

비슷하게 R(n)도 여러가지 다른 리소스가 될 수 있다는듯.

예를 들어서 메모리 사용량이라던가, 또는 필요한 기본적인 계산의 총량 이라던가

이런것들이 R(n) 필요한 리소스의 양으로 설정 될 수 있다.

책에서 설명하는 대략적인 정의는 아래와 같음.

R(n)은 아래의 조건을 만족할 때 order of growth Θ(f(n))을 가진다

k1 * f(n) <= R(n) <= k2 * f(n)

여기서 k1, k2, n은 서로 독립이다. n은 충분히 커야 한다.

음...

그렇군.

뭐, 모두에게 친숙한 빅 오 표기법... 이 아니라, 그 친척인 빅 세타 표기법을 설명하고 있는듯.

자세한 내용은 점근표기법 이라는걸 검색하면 다나옴.

매우 기본적인 내용이었구여

오늘은 여기까지

댓글 3