algorithm - 比较或替换操作的时间复杂度是多少？

Question

在估计某个算法的时间复杂度时，我们用伪代码来说:

for (int i=0; i<n; i++) ---> O(n)
  //comparison? ---> ?
  //substitution ---> ?
 for (int i=0; i<n; i++) ---> O(n)
  //some function which is not recursive

在这种情况下，这些指令的时间复杂度是O(n)，因为我们迭代输入n，但是比较和替换操作是恒定的吗？自从它们不依赖于n以来的时间？

谢谢

Answer 1

其他两个答案都假设您正在比较某种固定大小的数据类型，例如 32 位整数、 double 或字符。如果您使用像 < 这样的运算符在像 Java 这样的语言中，它们只能用于固定大小的数据类型，并且不能重载，那么这是正确的。但您的问题不是特定于语言的，并且您也没有说您正在使用此类运算符进行比较。

一般来说，比较操作的时间复杂度取决于您要比较的数据类型。例如，比较 64 位整数、 double 或字符需要 O(1) 时间。但作为反例，在最坏的情况下，按字典顺序比较字符串需要 O(min(k, k')) 时间，其中 k>, k' 是字符串的长度。

例如，这里是 String.compareTo 的 Java 源代码OpenJDK 7 中的方法，显然不需要恒定时间:

    public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }

因此，在分析基于比较的排序算法的时间复杂度时，我们通常会根据比较和替换的次数来分析其复杂度，而不是基本操作的次数；例如，selection sort执行 O(n) 次替换和 O(n²) 次比较，而 merge sort执行 O(n log n) 次替换和 O(n log n) 次比较。