问字符串比较时间复杂度

EN

字符串比较的时间为O(n)，n为字符串的长度。

但是，根据测试数据，您可以手动优化匹配算法。我已经提到了几个。

优化1:

检查两个字符串的大小，如果不相等，则返回false。因为这将停止进一步的O(n)比较，并节省时间。通常字符串数据结构将大小存储在内存中，而不是每次都计算它。这允许O(1)时间访问字符串大小。

实际上，这是一个巨大的优化。我将通过计算摊销时间复杂度来解释如何。

如果字符串数据结构可以有一个最大长度x的字符串，那么总共可以有(x + 1) (0，1，2，...，x)个可能的字符串大小。

有(x + 1) choose 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:

由于您的数据库包含web链接，因此它们可能属于同一网站，因此它们的前几个字符始终是相同的。这将导致多余的CPU时间使用。因此，对于这种情况，最好从末尾检查，因为相对链接只与末尾不同。

注意理论上讲，我们不是在开发一种算法来改变最坏情况下的时间复杂度，它仍然是O(n)。我们只是在优化算法。