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

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解决）
解决上面的题目的时候使用了这样一个方法。
varstr='上面那串字典';
varlineObj={};
vararr=str.split('\n');
for(vari=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)已经是最少的了。