假设您想计算文本中字符的出现次数。我能想到的最快方法是使用类似
unsigned char charcounts[256]
的数组,将其初始化为零,然后查看输入文本中的每个字符并执行charcounts[c]++
。然后使用两个变量进行线性搜索charcounts []
,以跟踪当前最低字符及其计数,当我们找到更低的字符/计数时,用新的字符/计数替换它,直到到达末尾。因此,"text"将被计算为t=2,e=1,x=1。有没有更快的方法来完成这个任务?
O(n)
,因为你至少要检查所有的输入。在此基础上,你可以讨价还价隐藏常数.. - phs