C++算法的執行時間

-5

如果我知道0,00096毫秒是地圖上的平均搜索時間，在C++中有290 024個元素我該如何計算具有1 000 000元素的地圖的搜索時間？C++算法的執行時間

我知道搜索算法的複雜性O（Log N）的映射和O（1）的Unordered_map。

它的複雜性已經線性比我可以只乘以時用1000 000/290024

你想問什麼？ –

我想知道當他們知道一個小的nbr的執行時間時，人們如何計算大型nbr的執行時間。在線性情況下，就像我說的那樣很容易。但我怎麼能做到這一點，如果它的O（logN）。 – user2975699

對於對數搜索，時間會

T ~= constant * log(N) 
T/log(N) ~= constant

所以估計時間T2尺寸爲N2給定的時間T1尺寸爲N1：

T2/log(N2) ~= T1/log(N1) 
T2 ~= T1 * log(N2)/log(N1) 
    ~= 0.00096ms * log(1000000)/log(290024) 
    ~= 0.00105ms

對於恆定時間哈希查找，時間不會改變。在實踐中，它可能不會是恆定的時間;但是沒有簡單的方法來估計它會是什麼。

2014-02-23 23:50:17

downvote的任何解釋？我相信這回答了這個問題，但請糾正我，如果它是錯誤的。 –

線性 - O（N），而不是O（1）或O（log n）的。如果您使用哈希映射搜索時間應該大約相同爲290 024和1000 000.具體結果取決於算法實現細節。

2014-02-23 23:43:45 Avt

回答