c - C 中的 strcmp 性能

Question

int myStrCmp (const char *s1, const char *s2) {
    const unsigned char *p1 = (const unsigned char *)s1;
    const unsigned char *p2 = (const unsigned char *)s2;

    while (*p1 != '\0') {
       if (*p2 == '\0') return  1;
       if (*p2 > *p1)   return -1;
       if (*p1 > *p2)   return  1;

       p1++;
       p2++;
     }

     if (*p2 != '\0') return -1;

        return 0;
}

这个比较是否有精确的符号 O(n)？当用 s1="abcd"s2="abcd."的两个字符串测量时。对于第一种情况和 s1="asdsdcvv" s2="asdsdcvv"。对于第二种情况，第二种情况是否恰好是第一种情况的两倍？

Answer 1

是的，这是在平均和最坏情况下的 O(n)，其中 n 是两个给定字符串中较短的一个的长度。您也可以将其表示为 O(min(m,n))，其中 m 和 n 分别是两个字符串的长度。

但不，O(n) doesn't mean that it needs exactly linear time .这意味着从最小问题规模开始，所有更大的问题都将低于某个线性函数。

如果您想了解更多细节，您需要一个非常详细的机器模型，这对于现代机器(缓存、分支预测、流水线、超线程等)来说似乎是不可能的。和操作系统(除非您使用的是没有多任务处理的非常简单的操作系统)。