判断字符串互为旋转的Java代码的算法复杂度是否为O(n)

你初步判断的O(n)复杂度并不准确，核心误差来自于对Java原生indexOf方法底层耗时的默认假设。

• 代码里各独立步骤的基础耗时拆解：
  • 空值校验：仅做引用判空，O(1)复杂度
  • 字符串长度对比：获取字符串长度是常数时间操作，O(1)
  • 拼接生成str1 + str2：两个长度为n的字符串拼接为长度2n的新串，这一步是严格的O(n)复杂度
• 最容易被忽略的indexOf环节耗时：

  很多人会默认字符串查找操作是线性耗时，但Java的String.indexOf从JDK6到主流长期支持版本的实现里，一直采用朴素字符串匹配算法，并没有使用KMP、BM这类能保证最坏线性复杂度的匹配方案

  • 最坏场景下，朴素匹配的时间复杂度是O(n²)：比如主串是连续n个a加一个b，待匹配串是连续(n-1)个a加一个b，每次匹配到最后一位失配时，都要把匹配窗口向前挪1位重新逐字符对比，累计的对比次数就是平方级
  • 只有在平均场景、字符串重复前缀很少的情况下，indexOf的耗时才会接近O(n)，和你初步的判断相符
• 顺带提一个代码实现的细节问题：
  现有判断条件(str1 + str2).indexOf(str2) > 0存在逻辑漏洞：当两个字符串完全相等（即偏移量为0的旋转场景）时，indexOf返回的匹配位置是0，会被这个条件误判为不匹配，正确的判断应该是匹配位置>=0即可。

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