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

Question

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

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的时候会更多。

Answer 1

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

Answer 2

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