2.4.1 常数级算法的性能
在分析算法性能时,本书常常会强调原生操作都具有常数级的性能。很明显,这个声明并不能完全准确地描述实际操作的性能,因为它没有考虑到硬件问题。例如,比较两个32 位的数x和y的大小,这个操作耗费的时间与x、y的大小无关。常数级的操作被认为具有O(1)的性能。
那么在比较两个256 位的数字时,性能又如何呢?比较两个1024位的数字又如何呢?我们认为,在长度k固定的前提下,比较两个k位数字的操作可以在常数时间内完成。这么认为的前提是问题的规模(即x、y的值)不得超过k。由k的倍增所导致的额外费用也被认为是O(1)的性能。