替代O（N^2）的時間與O（1）空間複雜度的複雜度在陣列

我想查看是否有任何替代蠻力算法（或稍有改善/最差表現的幼稚發現不同的值蠻力算法）仍然會導致O（N^2）時間複雜度和O（1）輔助空間。替代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 ）？

來源

2016-03-07 qwerty

排序使用堆排序和陣列停止，只要你找到兩個相同的元素：

O（NLogN）的時間複雜度
O（1）空間複雜度

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

選擇和插入排序有兩種選擇：

O（N×N個）的時間複雜度
O（1）空間複雜度

來源

2016-03-07 15:41:59

謝謝你的快速反應！我的問題，但是，因爲我尋找替代一個很奇怪的一個精確O（N^2）的時間複雜度的替代蠻力，而不是一個更好的解決方案。 – qwerty

選擇排序或插入排序就可以了就好了呢。更新了答案。 –

太棒了，謝謝！在這種情況下，我不太確定我的想法是否正確！ – qwerty

替代O（N^2）的時間與O（1）空間複雜度的複雜度在陣列

回答

相關問題