一個文本文件,大約有一萬行,每行一個詞,要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞,請給出思想,給出時間復(fù)雜度分析?
方案1:
如果文件比較大,無法一次性讀入內(nèi)存,可以采用hash取模的方法,將大文件分解為多個小文件,對于單個小文件利用hash_map統(tǒng)計出每個小文件中10個最常出現(xiàn)的詞,然后再進行歸并處理,找出最終的10個最常出現(xiàn)的詞。
方案2:
通過hash取模將大文件分解為多個小文件后,除了可以用hash_map統(tǒng)計出每個小文件中10個最常出現(xiàn)的詞,也可以用trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù),時間復(fù)雜度是O(nle)(le表示單詞的平準長度),最終同樣找出出現(xiàn)最頻繁的前10個詞(可用堆來實現(xiàn)),時間復(fù)雜度是O(nlg10)。