'효율성'에 해당되는 글 1건

  1. 2007.08.05 알고리즘 2

 

1.2-1 응용프로그램: 웹 브라우저, HTML을 읽어와서 태그에 맞게 해석하여 화면에 출력하는 알고리즘이 필요하다. HTML 태그를 읽어와서, 정규식 등을 이용해 파싱하고 이 엘리먼트에 대응하는 출력 형식을 판단한 후 화면에 나타내는 기능.


1.2-2 8n2 과 64nlgn 여기서 lgn=log2n이다. n이 무한히 커질 때, 8n2이 64nlgn보다 커질 것이고, 두 값이 같은 점이 8n2이 64nlgn을 앞지르는 지점이다. n 자리에 2의 거듭제곱 꼴을 넣고 그 수는 x라고 할 때 8n은 23+2x 64nlgn은 x*26+x이다.  x에 8을 대입할 경우 2의 지수가 19로 같다. 따라서 n은 28 즉 256보다 클 때 8n2이 64lgn보다 커진다.


1.2-3 100n2이 2n보다 클 경우 n의 최소치를 구하려면 대입해서 범위를 좁힌다. 14를 대입할 경우 100n2는 19600 2n는 16384가 나와서 앞 쪽이 크지만, 15를 대입하면 100n2는 22500 2n는 32678이 나와서 큰 정도가 뒤집어진다. 계산 횟수는 정수이므로, 최소값 n은 14이다.

이 글은 스프링노트에서 작성되었습니다.

신고
Posted by 세레

카테고리

분류 전체보기 (446)
Science (283)
ars boni et aequi (54)
Routine (83)
Language (23)
Q&A (1)
me2day (1)

달력

«   2017/10   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

티스토리 툴바