分析這個簡單算法的正確方法

給出文件中的一些字符串ab，abc，ad，ace，ddd ...，以確定某些字符串S是否在字符串中。如果我想用哈希來檢查是否存在S.算法分析：由於每個'put'操作都需要O（1）* K時間，其中K是字符串的長度，所以建立該地圖需要O（n * K）時間，其中n是字符串的數量。查找需要一定的時間，所以總體時間是O（n * k）。這是正確的想法嗎？雖然我們經常說散列表允許不斷查找時間，但它通常會忽略構建散列所花費的時間。當回答這樣的問題時，我應該說時間複雜度是O（n * k）還是O（n）？非常感謝。剛開始學習算法分析。分析這個簡單算法的正確方法

String line = null; 

BufferedReader br = new BufferedReader(new File("file.txt")); 
HashMap<String, Integer> strs = new HashMap<String,Integer>(); 
while((line=br.readLine()) != null){ 
    Integer count = strs.get(line); 
    if(count == null){ 
     strs.put(line, 1); 
    } 
    count++; 
} 

// Suppose the string to be checked is "str"; 
if(strs.contains(str)){ 
    return true; 
} 
return false;

來源

2014-01-27 user697911

當你說O（n）時，n與輸入大小成正比。但是，您在詢問是否聲明O（n * k），其中k也與輸入的大小成比例。在這種情況下，你真正說的是O（n^2） - 對於輸入K，算法可能需要時間t，但輸入2k需要4t的時間。這是你的意思嗎？

如果你只是想說算法對於k輸入需要t時間，對於2k輸入需要2t時間，那麼你簡單地說算法是O（n）。

現在來看算法......如果我正在解釋它，那麼這些步驟就是在讀取文件的同時構建哈希表，然後查找哈希表。通過文件的一個傳遞是O（n）將所有的字符串放在同樣是O（n）的哈希表中（假設散列表實現合理）。在散列表中查找一個條目是O（1）。所以總的來說，時間複雜度是O（n），與O（n）併發，加上O（1）...通常我們只是將其描述爲O（n），或者時間與大小成線性比例輸入。

來源

2014-01-27 19:21:09 user1445967

讓我們忽略我的代碼。一個文件包含一個字符串列表並檢查字符串中是否存在一個字符串。使用HashMap，時間複雜度是多少？這就是我想要回答的。對不起，這個問題。 – user697911

「K」意思是字符串的平均長度。 – user697911

編輯後給出以算法爲中心的答案，而不是以大-o以句法爲中心的答案:) – user1445967

分析這個簡單算法的正確方法

回答

相關問題