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