首页 > 字典统计分析,最佳时间复杂度能到达多少

字典统计分析,最佳时间复杂度能到达多少

有一堆字典,每一行为单个字典。
实现字典去重并统计次数。
如输入:

aaa
bbb
ccc
ddd
aaa
bbb
ccc
ddd
aaaa
bbbb
cccc
dddd

分析结果

aaa:2
bbb:2
ccc:2
ddd:2
aaaa:1
bbbb:1
cccc:1
dddd:1

这个题目,能做到的最佳时间复杂度是多少。先不考虑空间复杂度了。(因为按照下面的算法使用nodejs分析100W个单条数据(200W重复)时,15000ms-16000ms, 100+M的内存)

另外考虑下一个js的问题。(其实这个才是问题的重点 -_-| ,解决那个问题,不懂C/C++,所以nodejs解决)
解决上面的题目的时候使用了这样一个方法。

var str = '上面那串字典';
var lineObj = {};
var arr = str.split('\n');
for (var i = arr.length; i--;) {
  lineObj[arr[i]] = lineObj[arr[i]] ? lineObj[arr[i]] + 1 : 1;
}

这样子算是能够达到算法复杂度 O(N) 吗?
总觉得 lineObj[arr[i]] 在查询属性的时候总的耗费时间比 for 循环 arr的时候会更多。


从算法的角度说,最高效的应该是用Trie(字典树)这种数据结构,它能够实现一次遍历就去重并且统计出每个单词的个数,时间复杂度是O(l1 + l2 + ... + ln),li代表每个单词的长度,也就是俗称的O(n)。而你的实现用了哈希表,他的时间复杂度可以近似的认为是O(1),但是一般比O(1)要大一点。


js中对象都是用哈希表来存的,一般来说哈希表的搜索复杂度是O(1)的。
所以可以说你的算法复杂度是O(n)的,而且要完成你的任务至少遍历一遍,所以O(n)已经是最少的了。

【热门文章】
【热门文章】