这是算法导论中的一段话,我们还假设数据的每一个字（word）有着最大长度限制.例如,当处理规模为n的输入时,一般假定整数
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)的假设能成立.
相关问题
