The note of Legendre

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

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

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

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