算法问题约束是否改变时间复杂度？短字符串遍历复杂度疑问

问题约束确实会改变算法的时间复杂度，核心要看约束是否给输入规模设定了固定的常数上限。

拿你说的遍历字符串的例子来说：如果明确知道字符串长度永远小于15，那这个算法的时间复杂度就是O(1)，而非O(n)。

原因很简单：时间复杂度的本质是描述算法运行时间随输入规模增长的渐近趋势。当输入规模被限制在一个固定的常数范围内（这里最大是14个字符），不管输入的n具体是多少，算法的运行时间都不会超过一个确定的常数——哪怕n取到最大值14，遍历操作的次数也是固定的，不会随着n的增大而无限增长。这种情况下，算法的时间复杂度就属于常数时间O(1)。

如果没有这个约束，字符串长度可以无限增大，那遍历操作的次数会随n线性增长，这时候才是O(n)的时间复杂度。

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