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

Question

有一堆字典，每一行为单个字典。实现字典去重并统计次数。如输入：aaabbbcccdddaaabbbcccdddaaaabbbbccccdddd分析结果aaa:2bbb:2ccc:2ddd:2aaaa:1bbbb:1cccc:1dddd: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)已经是最少的了。