알고리즘 소개 서적에서 "c lg n"에 대해 혼동스러워합니다. c - 무엇입니까?

Question

나는 책 "알고리즘 소개"를 읽고 그리고 난이 부분에 의해 혼란 스러워요 :

우리는 또한 데이터의 각 단어의 크기에 제한을 가정합니다. 예를 들어, 크기가 n 인 입력에 대해 작업 할 때 우리는 일반적으로 정수가 몇 가지> 상수 c> = 1에 대해 c lg n 비트로 표현된다고 가정합니다. 각 단어가 n의 값을 유지할 수 있도록 c> = 1이 필요합니다.> 개별 입력 요소를 색인화 할 수있게하고,> size가 임의로 커지지 않도록 c를 상수로 제한합니다.

이 상수 C의 목적은 무엇입니까?

Answer 1

상수 c를 사용하는 이유는 거대한 단어 크기의 컴퓨터에서 작은 입력을 사용하는 경우입니다. 예를 들어, 64 비트 시스템에서 작업하면서 크기 입력 만 처리하는 경우 (예 : 2) lg n의 값은 12이지만 시스템은 64 비트 시스템입니다. 단어 크기가 정확히 12 비트라고 여기는 것은 옳지 않습니다. c의 추가 요소는 우리가 기계 단어 크기가 최소 1g 이상이지만 아마도 분석 결과를 엉망으로 만들지 않을 것이라고 가정 할 수 있습니다.

희망이 도움이됩니다.