这是算法导论中的一段话,我们还假设数据的每一个字（word）有着最大长度限制.例如,当处理规模为n的输入时,一般假定整数是由clgn位表示的,此处c为大于等于1的常量.之所以要求有c≥1,是因

Question

这是算法导论中的一段话,
我们还假设数据的每一个字（word）有着最大长度限制.
例如,当处理规模为n的输入时,一般假定整数是由clgn位表示的,此处c为大于等于1的常量.之所以要求有c≥1,是因为这样一个字就能容纳下n的值,从而可以引用每一个输入元素；之所以要求c为常量,是因为这样字长不会任意地增长.（如果字长可以任意地增长的话,就能在一个字中存储巨量的数据,并可以在常量时间内对它进行处理了,这显然是一种不真实的场景.）

Answer 1

我没有去看原文及上下文,不过看上去这段话的意思应该是比较清楚的.我给你举点例子辅助你理解,不过你还得把原文的上下文都看看.
在算法分析里经常会假定某些运算可以在O(1)时间内完成,比如说两个整数相加的运算,或者在一个数组中取出某个元素的操作.但这些假设需要基于一个更基本的假设——问题规模“不太大”.
比如说,通常两个32位整数相加确实只需要Θ(1)的时间,但是两个k位整数相加就需要Θ(k)的时间（甚至于存贮一个k位整数就需要Θ(k)的空间）,如果对整数的范围不加以限制的话“两个整数相加只需要O(1)时间”这句话显然是不合理的.
再比如,一般来讲对两个长度均为n的32位整数型数组对应的位置分别做某个位运算（如a[i]&b[i]）需要Θ(n)的时间.但毫无疑问一个长度为n的32位整型数组的数据量和一个32n位的大整数是完全一样的,如果对字长不加以限制的话这个问题就变成“对两个整数做位运算”,只需要O(1)时间,这又是一个不合理的结果.
所以对于某些比较隐含的数据规模需要做适当的假定,才能保证常用的关于O(1)的假设能成立.