由数组特定索引值决定迭代次数的for循环时间复杂度疑问

你的这段代码的时间复杂度既不是O(1)也不是O(n)，而是O(M)，其中M是数组最后一个元素arr[n-1]的值，原因如下：

• 时间复杂度的核心是衡量操作次数与输入规模的关联关系。通常我们说的O(n)里的n，指的是输入的规模（比如数组长度），但你的循环迭代次数完全由数组最后一个元素的数值决定，和数组长度n没有直接绑定：

  • 比如数组长度n=100，但最后一个元素是5，循环只执行5次；
  • 反过来，数组长度n=2，但最后一个元素是10000，循环要执行10000次。

• 你习惯用数组长度n来计算迭代次数是常见场景，但那是因为多数情况下操作次数和数组长度直接相关。但在这个案例里，操作次数的决定因素是数组元素的具体值，而非数组的长度，所以不能用n来定义复杂度。

• 补充说明：如果题目额外给出数组元素的大小和n存在关联（比如已排序数组的元素是从1到n的连续整数，此时arr[n-1]=n），那复杂度才会是O(n)。但题目里没有这个前提，所以默认要基于实际决定迭代次数的变量来分析。

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