Дополнительная сложность по времени 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 

Я знаю, что алгоритм грубой силы является ужасным решением, и есть много способов достижения гораздо более высокой производительности (с использованием наборов данных или достижением O (N) временная сложность и O (1) сложность пространства), однако из чистого интереса я пытаюсь найти сложную временную сложность O (N^2) и сложность пространства O (1). Возможно ли это?

Я думал, что могу применить алгоритм сортировки (например, Bubble или Insertion sort), а затем использовать цикл for, чтобы пройти через отсортированный массив, но это все равно даст мне квадратичную функцию, а не O (N^3)?

Answer 1

Сортировка массива с помощью пирамидальной сортировки и остановки, когда вы найдете два одинаковых элемента:

• O (NlogN) временная сложность
• O (1) пространство сложность

Вы можете также искать другие (более сложные алгоритмы) для этой цели here

Сортировка выбора и вставки 2 альтернативы с:

• O (NxN) временная сложность
• O (1) пространство сложность