了解关于机器字大小的假设在分析计算机算法 [英] Understanding assumptions about machine word size in analyzing computer algorithms

问题描述

我对托马斯H Cormen，查读的书算法导论 E. Leiserson，罗纳德属维斯特，克利福德·斯坦。在根据分析算法第二章中提到的是：

I am reading the book Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.. In the second chapter under "Analyzing Algorithms" it is mentioned that :

我们还假设上的数据的每个字的大小有限制。例如，对于尺寸为n的输入工作时，我们通常假设整数重新C> = 1 psented以c LG n位为一些恒定$ P $。我们要求C> = 1，使得每个字可保持n的值，使我们能够索引单个输入元件，并且我们限制c键是一个常数，使得字大小不随意生长（如果字长可以种植随意，我们可以存储大量的数据在一个字，它都在固定的时间进行操作 - 显然是不现实的情况下）

We also assume a limit on the size of each word of data. For example , when working with inputs of size n , we typically assume that integers are represented by c lg n bits for some constant c>=1 . We require c>=1 so that each word can hold the value of n , enabling us to index the individual input elements , and we restrict c to be a constant so that the word size doesn't grow arbitrarily .( If the word size could grow arbitrarily , we could store huge amounts of data in one word and operate on it all in constant time - clearly an unrealistic scenario.)

我的问题是，为什么这样的假设：每个整数应该重新presented用C LG n位，以及如何C> = 1既然如此使我们能够索引各个输入元素？

My questions are why this assumption that each integer should be represented by c lg n bits and also how c>=1 being the case allows us to index the individual input elements ?

推荐答案

首先，由 LG 他们显然意味着日志基地2个，所以 LGñ 是位的数量 N 。

first, by lg they apparently mean log base 2, so lg n is the number of bits in n.

然后他们要说的是，如果他们有一个算法，取号的列表（我是更具体的在我的例子，以帮助更容易地理解），如 1,2,3 ，... N 然后他们认为：

then what they are saying is that if they have an algorithm that takes a list of numbers (i am being more specific in my example to help make it easier to understand) like 1,2,3,...n then they assume that:

• 在内存中一个字是大到足以容纳所有这些数字。

• a "word" in memory is big enough to hold any of those numbers.

在内存中一个字是不是大到足以容纳的所有的数字（以一个字，装在某种程度上）。

a "word" in memory is not big enough to hold all the numbers (in one single word, packed in somehow).

计算步骤中的算法的数量，在一个字的操作时所要采取的一个步骤。

when calculating the number of "steps" in an algorithm, an operation on one "word" takes one step.

他们这样做的原因是，保持分析现实的（你只能存储数量最多的原生类型的一些尺寸;之后，你需要切换到任意precision库），而不选择一个具体的例子（类似于32位整数），可能是不恰当的在某些情况下，或成为过时的。

the reason they are doing this is to keep the analysis realistic (you can only store numbers up to some size in "native" types; after that you need to switch to arbitrary precision libraries) without choosing a particular example (like 32 bit integers) that might be inappropriate in some cases, or become outdated.

这篇关于了解关于机器字大小的假设在分析计算机算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！