如何统计该大写字母计数算法中的比较操作总次数？

比较操作统计规则 #

我们通常按两种口径统计比较操作次数，你可以根据需求选择对应计算方式：

• 仅统计业务核心比较：仅计算if语句的字符相等判断，这也是算法性能分析最常用的统计口径
• 全量比较统计：包含循环条件判断、if判断在内的所有比较操作

你的代码的比较次数计算 #

首先明确固定参数：你的capitalLetters数组存储了26个大写英文字母，长度固定为26，设输入字符串的长度为n。
注意：你当前的实现没有在匹配到大写字母后添加break终止内层循环，所以不管字符是否匹配，内层循环都会完整执行所有26次遍历。

口径1：仅统计核心if比较 #

外层循环遍历每一个字符串字符，共执行n次，每次外层循环对应内层26次相等判断：
总比较次数 = n * 26
你示例中使用的字符串"Wonderfull World"长度为16，代入得：16 * 26 = 416次

口径2：全量比较统计 #

除了if的相等判断，两层for循环的边界判断也属于比较操作：

1. 外层循环i < str.length()：共执行n + 1次（最后i等于n时判断不满足，退出循环）
2. 内层循环j < capitalLetters.length：每次外层循环对应执行26 + 1 = 27次，n次外层总共有n * 27次
3. if相等判断：共n * 26次
   总比较次数 = (n + 1) + 27n + 26n = 54n + 1
   示例代入得：54 * 16 + 1 = 865次

可优化方向 #

• 内层循环匹配到大写字母后添加break跳出，可大幅减少平均比较次数：最好情况（所有字符都是'A'）仅需n次比较，最坏情况仍为26n次，平均约13n次
• 更推荐直接通过字符ASCII范围判断，去掉内层循环，实现如下：

char c = str.charAt(i);
// 仅需2次比较即可判断是否为大写字母
if (c >= 'A' && c <= 'Z') {
    count++;
}

这种实现的核心比较次数仅为2n，常数项远低于双层循环方案，性能更优。

内容的提问来源于stack exchange，提问作者Martin Mulyo Syahidin