替代O（N^2）的时间与O（1）空间复杂度的复杂度在阵列

Question

我想查看是否有任何替代蛮力算法（或稍有改善/最差表现的幼稚发现不同的值蛮力算法）仍然会导致O（N^2）时间复杂度和O（1）辅助空间。

这是我的蛮力伪代码：

procedure distinct(Input: array)        
     for i=0 to i < length of array      
      for j=i+1 to j < length of array     
       if array[i] == array[j] and i != j then 
        return false       
       end if 
       increment k 
      end for 
      increment j 
     end for 
     return true 
    end procedure 

我知道蛮力算法是一个可怕的解决方案，有（使用的数据集或实现Ø实现更好的性能的许多方面（N）的时间复杂度和O（1）空间复杂度），但出于纯粹的兴趣，我试图找到O（N^2）最坏情况下的时间复杂度和O（1）空间复杂度。它甚至有可能吗？我认为我可以应用排序算法（例如Bubble或Insertion排序），然后使用for循环遍历排序后的数组，但是仍然会给我一个二次函数而不是O（N^3 ）？

Answer 1

排序使用堆排序和阵列停止，只要你找到两个相同的元素：

• O（NLogN）的时间复杂度
• O（1）空间复杂度

你也可以找用于此目的的其他（更高级的算法）here

选择和插入排序有两种选择：

• O（N×N个）的时间复杂度
• O（1）空间复杂度