降低數組中最大重複元素的複雜度

Question

我在考試前得到了一個要做的練習列表，他們沒有評分，這就是爲什麼我沒有將他們標記爲家庭作業。

該算法採取鑑於這種算法號碼

的數組：

  Algo-X(A) 
       i=1 
       j=1 
       m=0 
       c=0 
       while i ≤ |A| 
        if A[i] == A[j] 
         c=c+1 
        j=j+1 
        if j > |A| 
         if c > m 
          m=c 
         c=0 
         i=i+1 
         j=i 
       return m 

問題1：分析ALGO-X的複雜性。

問題2：編寫一個與Algo-X完全一樣的算法，但是具有嚴格更好的漸近時間複雜度的算法。

現在，這個時間複雜度是O（n^2）對不對？

算法本身從我理解的數組中搜索內容並返回數組中最大重複數的個數。

我該如何降低複雜性？

我不能認爲有一個數字是N/2次出現。

Thanks guys guys

Answer 1

現在，這個時間複雜度是O（n^2）對不對？

是的，你說得對。 j將遍歷從i到|A|的所有元素，每i從1到|A|。

∑ _{i = 1 .. | A |} ∑ _{j = i .. | A | （j）= O（| A | ）= O（n ）。}

如何降低複雜性？

您可以先排序初始數組。然後所有相同的數字將順序發生。你只是尋找最長的一組相等的元素。

sort(A) 
m = 1 
c = 1 
i = 2 
while i ≤ |A| 
    if A[i] == A[i - 1] 
     c = c + 1 
    else 
     c = 1 
    if c > m 
     m = c 
    i = i + 1 

排序的時間複雜度爲O（n * log（n）），排序數組的工作時間爲O（n）。總的時間複雜度將是O（n * log（n））。

Answer 2

這個問題很容易在線性時間和線性空間解決---例如，通過使用散列表。這裏的一個僞代碼：

HashTable<Integer, Integer> H = new HashTable<Integer,Integer>(); 
int res = 0; 
for (int i = 0; i < A.length; ++i) { 
    if (H.contains(A[i])) { H[A[i]] = 1; } 
    else { H[A[i]] += 1; res = Math.max(H[A[i]], res); } 
} 

return res 

它也可解在O(n log n)時間（甚至在O(n)時間，如果在A數目足夠相似），並通過分選，然後掃描該陣列O(1)空間。

sort(A) 
i = j = 0; 
res = 0; 
while i < |A| do 
    j = i+1 
    while j < |A| && A[i] == A[j] do 
     j = j+1 
    done 
    res = max(res, j-i+1) 
    i = j 
done 
// Separately handle the case when |A|=1 
if |A| = 1 then 
    res = 1 
end 
return res 

更妙的是，如果在A元素的最大區別是爲了|A|，您可以在線性時間使用counting sort（或其他一些integer sorting algorithm）排序A。然後該算法以線性時間運行。