为何该数组遍历算法中toUpperCase被判定为O(1)时间复杂度？

你的分析是对的：toUpperCase()和toLowerCase()确实需要遍历字符串的每个字符完成转换，单独看它们的时间复杂度是O(M)，其中M是目标字符串的长度。书中将它们视为O(1)并得出整体复杂度O(N)，通常是以下几种原因：

• 简化假设：很多算法书籍会做场景简化，如果题目隐含所有输入字符串的长度M是固定常数（比如处理固定长度的编码、短标识），那么O(M)就可以等价于O(1)。此时整体复杂度由数组遍历次数N主导，表述为O(N)。
• 核心维度优先：如果问题的核心变量是数组长度N，而字符串长度M并非关注的核心增长维度（比如M的增长远慢于N，或M在问题中是次要因素），作者会将字符串处理的复杂度合并为常数项，从而突出核心逻辑的复杂度趋势。
• 工程近似：在实际开发场景中，若字符串长度的上限固定，toUpperCase()的实际开销不会随N变化而线性增长，此时将其视为常数时间是合理的近似，能更直观地描述算法的性能特征。

不过严格来说，这段代码的精确时间复杂度应该是O(N*M)，其中N是数组长度，M是数组中字符串的平均长度。书中的表述是一种简化后的近似，而非严格的复杂度推导。

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