Java字符校验函数Big O时间复杂度计算咨询

平均时间复杂度为 O(m + l)，其中 m 为 message 的长度，l 为 lettersFinded 的长度。

复杂度拆解分析 #

• 第一步长度判断：lettersFinded.length() >= message.length() 是O(1)操作，不占复杂度权重。
• 两次调用makeMaps方法：
  • makeMaps内部遍历输入字符串的每一个字符，对每个字符执行的HashMapcontainsKey、get、put操作，平均场景下均为O(1)时间开销，忽略空格过滤的常数级判断，处理长度为k的字符串的时间复杂度为O(k)。
  • 统计message的字符计数开销为O(m)，统计lettersFinded的字符计数开销为O(l)。
• 遍历message的字符计数Map校验数量：
  • 该Map的entry数量最多等于message的不同字符数，上限为m，每个getOrDefault操作平均O(1)，整体开销为O(m)，低于前面O(m + l)的量级，不影响整体复杂度。

之前判断的误区 #

你之前认为复杂度是O(n)且n等于message.length()，是因为忽略了统计lettersFinded字符计数的开销：如果lettersFinded的长度远大于message（比如你的第一个测试用例里，message长度是6，lettersFinded长度超过20），这部分的开销是不能省略的。

补充说明 #

如果是讨论HashMap最坏场景（极端哈希冲突下），单次操作开销会上升到O(log k)（k为单个哈希桶的元素数量，Java 8+用红黑树优化后），但在常规的算法复杂度分析、作业评分场景中，均默认HashMap的基础操作为O(1)平均复杂度。

内容的提问来源于stack exchange，提问作者Maxime Alza