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

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 位整数、双精度数或字符。如果您使用像<Java 这样的语言中的运算符，它们只能用于固定大小的数据类型，并且不能重载，那么这是正确的。但您的问题不是特定于语言的，而且您也没有说您正在使用此类运算符进行比较。

\n\n

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

\n\n

例如，下面是String.compareToOpenJDK 7 中该方法的 Java 源代码，它显然不需要常数时间：

\n\n

    public int compareTo(String anotherString) {\n        int len1 = value.length;\n        int len2 = anotherString.value.length;\n        int lim = Math.min(len1, len2);\n        char v1[] = value;\n        char v2[] = anotherString.value;\n\n        int k = 0;\n        while (k < lim) {\n            char c1 = v1[k];\n            char c2 = v2[k];\n            if (c1 != c2) {\n                return c1 - c2;\n            }\n            k++;\n        }\n        return len1 - len2;\n    }\n

\n\n

因此，在分析基于比较的排序算法的时间复杂度时，我们常常从比较和替换的次数来分析其复杂度，而不是从基本操作的数量来分析；例如，选择排序执行 O( n ) 替换和 O( n \xc2\xb2) 比较，而合并排序执行 O( n log n ) 替换和 O( n log n ) 比较。

\n

Answer 2

首先，阅读这本书。这是这个主题的很好的解释。

1. 比较。例如，我们有两个变量a和b。当我们这样做时，我们只需从内存中a==b取出a和b并比较它们。让我们将“ c ”定义为内存成本，将“ t ”定义为时间成本。在本例中，我们使用2c（因为我们使用内存的两个单元）和1t（因为只有一个具有恒定成本的操作），因此1t - 是常数。因此时间复杂度是恒定的。
2. 代换。和之前的操作基本一样。我们使用两个变量和一个操作。该操作对于任何类型都是相同的，因此替换的时间成本是恒定的。那么复杂性也是恒定的。