我的代碼的Big-O複雜性是什麼？

鑑於整數數組，寫一個返回所有唯一對這些加起來100我的代碼的Big-O複雜性是什麼？

實例數據的方法：

sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51] 
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]]

我這個週末解決這個問題，而我的解決辦法似乎可擴展性和高效，我想確定我的解決方案最糟糕的時間複雜性是什麼？

這裏是我的解決方案：

def solution(arr) 
    res = [] 
    h = Hash.new 

    # this seems to be O(N) 
    arr.each do |elem| 
    h[elem] = true 
    end 

    # how do I determine what Time complexity of this could be? 
    arr.each do |elem| 
    if h[100-elem] 
     h[100-elem] = false 
     h[elem] = false 
     res << [elem, 100-elem] 
    end 
    end 
    res 
end

如果這兩個循環是O（N）各的，我把它們加起來：O（N + N），這將等於O（2N）和服用2是一個常數，我可以假設我的解決方案是O（N）？

來源

2013-12-16 Jasdeep Singh

這是正確的。 – screenmutt

我認爲你的假設基本上是正確的。這也是假設元素可以是負數（超過100），因爲這是有意義的 - 否則只有重複初始輸入纔會有任何縮放成本，並且一旦您填充所有鍵0，其他所有內容都可以被視爲固定成本。 100。從技術上講，'h [elem] = true'不是'O（1）'（很多人似乎都假設），而是'O（log（N））'，所以你的整體複雜性可能是'O（Nlog（N））'最糟糕的情況 - 你只能看到如果你用數百萬個整數抽取數組，但是 –

@NeilSlater你錯了。 'h'是一個哈希映射，其搜索是線性時間。 [Wiki]（http://en.wikipedia.org/wiki/Hash_table） – screenmutt

你是對的。如果考慮使用散列搜索/插入的分期運行時間，則此代碼的大-O將爲O(n)。

如果您採用散列搜索/插入的真實最差情況（O(n)），那麼它將是O(n^2)。

See Wikipedia on Hash Tables

來源

2013-12-16 16:25:28 screenmutt

的問題可被詢問散列的時間複雜度，但對於特定的問題，該散列會更好，因爲由輸入0..sum（100在這種情況下編入索引的bool的陣列實現）。這將有最佳，最差和平均情況下的恆定時間。

該方法計算O（N）的複雜性更簡單。

來源

2013-12-16 17:11:40 danh

是的，這是實施解決方案的另一種方式。我也想到了這種方法。 –

我想你會發現它在實踐中更快（以及更復雜的計算）。稀疏陣列在速度上交易一點空間（幾乎沒有低N）。 – danh

我的代碼的Big-O複雜性是什麼？

回答

相關問題