時間複雜度和運行時間之間的關係是什麼？

我目前正在使用leetcode爲面試做準備。這是我遇到的問題，非常簡單。兩個總：時間複雜度和運行時間之間的關係是什麼？

鑑於NUMS = [2，7，11，15]，目標= 9，

由於NUMS [0] + NUMS [1] = 2 + 7 = 9，返回[0 ，1]。

這裏是我的解決方案，其時間複雜度爲O（n），空間複雜度爲O（n）。 enter image description here

詳細信息顯示它的運行時相當緩慢，甚至被O（n）^ 2解決方案打敗。

我想當然地認爲較低的時間複雜性意味着更快的運行時間。現在我很困惑。運行時間和時間複雜度之間有什麼關係？面試中預計會有什麼樣的解決方案？

將來，將您的代碼作爲文本從IDE複製並粘貼到問題中。圖像不能被搜索引擎索引，還有其他問題。有關討論，請參閱https://meta.stackoverflow.com/q/285551/215552。 –

如果給定nums = [2,3,3,5]和6的目標，那麼解決方案是nums [1] + nums [2]，但是你的代碼將無法找到它，因爲Map不允許重複。正確性第一，表現第二。 –

我認爲理所當然的是，較低的時間複雜度意味着更快的運行時間。

並不總是如此。這取決於問題的大小，n。時間複雜性描述了性能，因爲n漸近地增長到無窮大。

就你的情況而言，n太小，不足以使時間複雜度影響運行時。有關更長的解釋，請參閱Difference between Time Complexity and Running time。

我對這種行爲的解釋是你使用了一個散列表，而另一個解決方案沒有。結合n足夠小的事實，他們的表現可以相媲美。

對不起，您需要撥打containsKey()？我想不是，只要檢查put()返回什麼，如hashmap containsKey complexity中所述。

2017-05-09 16:03:07 gsamaras

非常感謝，我從你的答案中學到很多東西。 – pandakillsalot

@pandakillsalot太棒了！你問了一個很好的問題，這就是爲什麼我upvoted。不要忘記*接受*答案。隨着你的經驗增長，你會感覺更好的時間複雜性真的意味着什麼！ ;） – gsamaras

在這種情況下，他應該檢查'get（）'返回的內容，而不是'put（）'返回的內容。 –

回答