Zip*_*Zip 1 string comparison time-complexity
哪个比较需要更长的时间？
a = helloworldhelloworldhelloworld
b = https://www.somerandomurls.com/directory/anotherdirectory/helloworld.html
if a != b:
doThis()
相对
a=one, b=two
if a != b:
doThis()
我经常需要对照我的数据库进行检查，该数据库有数千行。我不是在寻找任何特定的编程语言。我只想知道哪个比较需要更快。如您所见，b第一个示例中的值更长，而第二个示例中的值更短。所以我想知道这是否会对比较产生任何影响。
字符串比较通常对字符进行线性扫描，在字符不匹配的第一个索引处返回 false。
时间复杂度为 O(N)，实际花费的时间取决于在统计上出现差异之前需要扫描多少个字符。如果您的每个字符串都以 http:// 开头，则扫描前 7 个字符将产生恒定的开销（无需针对您的专用数据定制比较算法）。
如果您有很长的字符串，许多字符串的开头倾向于具有相同的起始字符，并且有极端的性能要求，您可以考虑对字符串进行散列，首先比较散列，如果散列匹配，则只对字符串进行线性比较（为了排除哈希冲突的可能性）。如果您使用比假定的长字符串更短的哈希值进行初始比较，您可以通过仔细设计查询策略来减少系统的 IO 和 RAM 要求。
小智 5
字符串比较的时间是 O(n)，n 是字符串的长度。
但是，根据测试数据，您可以手动优化匹配算法。我提到了一些。
优化一：
检查两个字符串的大小，如果不相等，则返回 false。因为这将停止进一步的 O(n) 比较，并节省时间。通常字符串数据结构将大小存储在内存中，而不是每次都计算。这允许 O(1) 时间访问字符串大小。
实际上，这是一个巨大的优化。我将通过计算摊销时间复杂度来解释如何。
如果您的字符串数据结构可以有一个最大大小为 x 的字符串，那么总共可以有(x + 1) 个可能的字符串大小（0, 1, 2, ... , x）。
有(x + 1) 选择 2种方式选择两个字符串 = x * (x + 1) / 2
如果使用优化 1，则仅当两个字符串长度相等时才需要比较整个长度。只有x + 1 个这样的情况。完成的操作数将为0 + 1 + 2 + .... + x = x * (x + 1) / 2。
剩余的(x + 1) * (x - 2) / 2 个案例将在 O(1) 时间内计算。
因此总计算 = x * (x + 1) / 2 + (x + 1) * (x - 2) / 2 = (x + 1) * (x - 1)即 O(n^2)。由于我们正在进行 x * (x + 1) / 2 个字符串比较，因此每次比较的摊销时间复杂度为 O(1)。
如果没有任何优化，就会有
0 + 1 * (x) * 1 + 2 * (x - 1) * 2 + 3 * (x - 3) * 3 + .... + x/2 * x/2 * x/2计算。毫无疑问，这将超过 O(n^3)。并且摊销时间复杂度将超过 O(n)。
优化2：
由于您的数据库包含网络链接，它们可能属于同一个网站，因此它们的前几个字符将始终相同。这将导致冗余的 CPU 时间使用。因此，对于这种情况，最好从末尾进行检查，因为相对链接仅与末尾不同。
注意 从理论上讲，我们并不是在开发一种会改变最坏情况时间复杂度的算法，它仍然是 O(n)。我们只是在优化算法。