是否存在O(sumof(n))时间复杂度？该写法是否符合算法规范？

复杂度写法规范说明 #

不存在标准认可的O(sumof(n))时间复杂度写法，该表述不规范。如果你的实际含义是1到n的整数求和，标准大O表示法需要化简为最高阶形式，也就是O(n²)；如果确实需要在推导过程中展示求和逻辑，可以写成O(Σ_{i=1}^n i)，最终给出结论时仍需化简为多项式形式。

你提供的最长回文子串算法的复杂度计算 #

你的算法逻辑分为两层：

• 外层checkIter递归遍历所有起始下标，共执行n次（n为输入字符串长度）
• 内层check调用逐次缩短右边界查找以当前下标为起点的最长回文，每次判断回文的操作时间和当前子串长度成正比

最坏情况下总操作量就是n + (n-1) + (n-2) + ... +1 = n(n+1)/2，正好对应你给出的测试用例结果：长度为4的输入运行10次，长度为5的输入运行15次，完全匹配求和结果，最终时间复杂度为标准的O(n²)。

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