为什么比较字符串0（n），但是比较数字0（1）？

Question

我知道要比较两个字符串是否相等，解释器必须遍历两个字符串并比较每个字符。

这将使时间复杂度0(n)，其中n是最短字符串的长度。

但是，比较两个数字是否相等是0(1)。

为什么？解释器是否不必遍历每个数字以检查是否相等？

Answer 1

计算机中的数字通常以固定大小的单位处理。在任何给定的语言和/或编译器/平台组合中，int可能是32或64位，但永远不会是可变长度。

因此，比较数字时，您要比较的位数是固定的。

另一方面，字符串具有固有的可变长度，因此您只说“字符串”并不能告诉您必须比较多少位。

但是有[[are个例外，因为存在可变长度的数字，通常称为BigInteger或BigDecimal之类的东西，其行为与String比较非常相似，因为它最终可能是O（n）比较两个BigDecimal值是否相等。

Answer 2

通常程序将数字表示为固定大小的数据结构（二进制值，这就是为什么您可能会看到它们的大小以位描述）的原因。由于是固定大小的，比较将花费恒定的时间，并且为O（1），这是这种表示的好处之一。不利的一面是限制了可以表示的值的范围。

解除此限制的替代表示形式，允许任意大范围的数字，因此不再固定大小，也不再是O（1）进行比较。

Answer 3

String

字符串比较通常是对字符的线性扫描，在字符不匹配的第一个索引处返回false。

时间复杂度为O（N），实际花费的时间取决于在统计上出现差异之前需要扫描多少个字符。没有一个简单的答案，但是答案仍然很明显;-）

数字

如果两个整数相等，那么不比较所有位就不可能知道。因此，在相等的情况下，所需的时间与位数成正比（如果N是比较数之一，则它与log（abs（N））成正比）。

如果它们实际上不相等，则有很多情况都与实现内部相关。长整数以2的幂为单位存储为“数字”向量。如果向量的长度不同，则int不相等，这需要固定的时间。

但是如果它们的长度相同，则必须对“数字”进行比较，直到找到第一对（如果有）不匹配的对。这花费的时间与需要比较的位数成正比。

Answer 4

（（1）我比较字符串（具有41个字符）

A quick brown fox jumps over the lazy dog

和
A lazy dog jumps over the quick brown fox

在最坏的情况下，我必须比较41个字符。这是O（n）复杂度。 （在最坏的情况下n次操作）
（（2）

当我比较两个数字42和24时，我需要一个动作，结果是42 > 24。这是O（1）复杂度（在最坏的情况下为1个动作）。