判断a^nb^n模式字符串的函数时间复杂度是否为线性？

首先直接给结论：没错，这个函数确实属于线性时间复杂度O(n)

咱们来拆解一下为什么：

• 大O时间复杂度的核心是描述算法运行时间随输入规模增长的趋势，它会忽略所有常数系数和低阶项——因为当输入规模变得极大时，这些常数对整体增长的影响微乎其微。
• 假设你输入的字符串长度为n，循环运行n/2次？这完全不是问题。比如当n=10^6时，循环跑50万次，运行时间依然和输入长度n成严格的正比例关系，这就是线性时间的典型特征。
• 顺便说下这类函数的常见实现：一般是用左右双指针，左指针从字符串头部找a，右指针从尾部找b，每匹配一对就往中间移动，直到指针相遇或者发现不匹配的情况。这种逻辑下，每个字符最多被访问一次（或者说每个指针移动的总次数是O(n)），整体时间复杂度自然是线性的。

所以哪怕循环只跑了n/2次，它依然符合线性时间复杂度的定义——大O表示法不关心你具体跑了多少次，只关心增长速率和输入规模的关系。

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