这是线性时间还是二次时间?使用相同的循环进行多次迭代

Question

这是一个多个指针的黑客实现，用于找出数组是否包含唯一值。但我这样做的方式是多次循环遍历它，跳过 OG 指针。

这是线性的还是二次的？

function uniqueAll(arr) {
let i = 0
for (let j = 1; j < arr.length; j++) {
console.log(`i: ${arr[i]} j: ${arr[j]}`)
if (j === i) continue;
if (j === arr.length - 1 && i < arr.length - 1) {
i++
j = 0
}
if (arr[j] === arr[i]) 
return false
}
return true
}

是的，我知道它可以像以下一样简单：

let isUnique = (arr) => [... new Set(arr)].length === arr.length

我正在探索其他选择。

Answer 1

它是二次的，O(n²(。你的 j 计数器递增，直到你到达数组的末尾，所以 n 次，但随后你递增 i 并将 j 重置为 0，再次开始，直到 i 也达到数组的长度。这等效于嵌套循环。

Answer 2

对于包含所有唯一项的数组，它将为每个项运行一个循环。因此，最坏情况的复杂性绝对是二次的。