时间复杂度是 O(n) 还是 O(n^2)？

Question

感觉自己写的这个js函数的时间复杂度是O(n)，但同时又感觉是O(n^2)。正确的时间复杂度是多少？该函数应该找到找到的第一个重复项的最后一个索引。例如，在第一个示例中，在索引 0 处找到了 1，在索引 6 处也找到了 1。因此结果将为 6，因为这是该数组中第一个重复值的最后一个索引。如果没有找到重复项，那么我们 return -1.

// [1, 2, 4, 5, 2, 3, 1] --> output: 6
// [1, 1, 3, 2, 4] --> output: 1
// [1, 2, 3, 4, 5, 6] --> output: -1(not found)
// It can be in any order, just need to find the last index of the first duplicate value thats there

const findFirstDuplicateIndex = (arr) => {
    let ptr1 = 0
    let ptr2 = 1   
    while (ptr1 < arr.length - 1) { // O(n)
        if(arr[ptr1] === arr[ptr2]) {
            return ptr2 + 1
        } else {
            ptr2++ 
        }
        if (ptr2 === arr.length - 1) {ptr1++; ptr2 = ptr1 + 1}
    }
   return -1
}

Answer 1

在时间复杂度概念中，我们必须为循环声明分配一个 1 值，我们必须检查条件，然后我们必须检查它将运行和 return 的次数我们必须加 1 的任何值，完成后我们必须添加 alll .

Answer 2

你的代码的时间复杂度是O(n^2).

您的代码是两个嵌套循环的另一个版本。

if (ptr2 === arr.length - 1) {ptr1++; ptr2 = ptr1 + 1}

这段代码相当于添加了一个嵌套循环，即

for(ptr2 = ptr1+1; ptr2 < arr.length; ; ++ptr2)

如果我们用两个嵌套的 for 循环重写您的代码，我们有

const findFirstDuplicateIndex = (arr) => {
    for(let ptr1=0; ptr1 < arr.length - 1; ++ptr1) {
      for(let ptr2=ptr1+1; ptr2 < arr.length; ++ptr2){
        if(arr[ptr1] === arr[ptr2]) {
            return ptr2
        }
      }
    }
    return -1;
}

现在，

For the 1st iteration: the inner loop will cost N-1.
For the 2nd iteration: the inner loop will cost N-2.
For the 3rd iteration: the inner loop will cost N-3.
........................
........................
For the (N-1)th iteration: the inner loop will cost 1.

因此，总时间复杂度是成本的总和

(N-1) + (N-2) + (N-3) + . . . . + 1

这是一个等差级数，使用算术和公式我们有

(N-1) + (N-2) + (N-3) + . . . . + 1 = (N-1)*(N-2)/2 = O(N^2)

因此，你的代码的时间复杂度是O(n^2).

Answer 3

不管你怎么写，最终。您的代码运行来自 0..n-2 的变量 arr1 和来自 arr1+1..n-1 的每个 arr1 的变量 arr2。这会产生 O(N^2)（最坏情况）时间复杂度。

但是由于更复杂的算法不容易被发现，一个好的评估复杂性的方法是使用算法的检测版本，您只需计算步骤数即可。并使用病理学上最坏情况的数据作为输入。

在您的情况下，最坏的情况是，当重复项位于数组中的最后 2 个值时（例如 [5 4 3 2 1 1]）。

因此，在第 1 步中，为自己编写一些测试数据生成器：

(defun gen-test-data (n)
  (make-array (+ n 1)
          :initial-contents
          (append
           (loop for x from n downto 1
             collecting x)
           '(1))))

它在长度为 (n+1) 的数组中生成病态模式。

(gen-test-data 20)
#(20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1)

接下来，编写您的检测算法，其中 returns 一些额外信息：

(defun first-duplicate (data)
  (let* ((arr (etypecase data
                 ((simple-vector *) data)
                 (cons (make-array (length data)
                                   :initial-contents data))))
         (n (array-dimension arr 0)))
    (loop
      with counter = 0
      for i0 below (- n 1)
      do (loop
       for i1 from (+ i0 1) below n
       do (when (= (aref arr i0) (aref arr i1))
        (return-from first-duplicate
          (list :value (aref arr i0)
            :i0 i0
            :i1 i1
            :counter counter
            :n n)))
       do (incf counter)))))

我在这里选择了嵌套循环符号，因为无论如何你都会这样做。

现在的最后一步是运行各种 n 的函数，因此您可以看到 n 与 counter 的关系：

(loop for n from 2 to 100 by 10 collecting (first-duplicate (gen-test-data n)))
((:VALUE 1 :I0 1 :I1 2 :COUNTER 2 :N 3)
(:VALUE 1 :I0 11 :I1 12 :COUNTER 77 :N 13)
(:VALUE 1 :I0 21 :I1 22 :COUNTER 252 :N 23)
(:VALUE 1 :I0 31 :I1 32 :COUNTER 527 :N 33)
(:VALUE 1 :I0 41 :I1 42 :COUNTER 902 :N 43)
(:VALUE 1 :I0 51 :I1 52 :COUNTER 1377 :N 53)
(:VALUE 1 :I0 61 :I1 62 :COUNTER 1952 :N 63)
(:VALUE 1 :I0 71 :I1 72 :COUNTER 2627 :N 73)
(:VALUE 1 :I0 81 :I1 82 :COUNTER 3402 :N 83)
(:VALUE 1 :I0 91 :I1 92 :COUNTER 4277 :N 93))

输出现在清楚地表明，它不能是 O(N)，而是 O(N^2)。

时间复杂度是 O(n) 还是 O(n^2)？

Is Time complexity O(n) or O(n^2)?

algorithm

data-structures

time-complexity