递归找最小值算法时间复杂度分析：为何findmin是O(n²)？

首先，我先补全你没写完的findmin函数（推测完整实现如下）：

int findmin(const int a[], int n) {
    cnt++;
    if(n == 0)
        return a[0];
    int min;
    return a[n] < (min = findmin(a, n-1)) ? a[n] : min;
}

先提个关键bug：你在main里创建的数组是int arr[num];（num=100），数组合法索引是0~99，但你调用findmin(arr, num)时传入的n=100，会导致a[n]访问arr[100]，属于数组越界行为，正确的调用应该是findmin(arr, num-1)。

回到你的核心问题：为什么有人说这个函数的时间复杂度是O(n²)？其实这个说法是错误的，我们一步步拆解分析：

1. 递归调用次数是线性的 #

当传入修正后的n（比如99）时，findmin会递归调用自己n次，加上最开始的那次调用，总共是n+1次调用。比如n=99时，最后cnt的输出是100——调用次数和n是严格线性关系，也就是O(n)级别。

2. 每次调用的操作都是常数级 #

每次进入findmin函数，除了递归调用外，只做了：

• 一次赋值操作（min = findmin(...)）
• 一次比较操作（a[n] < min）
• 一次三元运算符的判断返回

这些都是O(1)的常数操作，没有嵌套循环、嵌套递归或者其他会增加时间开销的逻辑。

3. 总时间复杂度计算 #

总时间复杂度 = 调用次数 × 每次调用的操作量 = O(n) × O(1) = O(n)，完全不是平方级。

为什么会有人误以为是O(n²)？ #

可能有两种常见误解：

• 把这个递归实现和另一种低效的找最小值方式搞混了：比如如果每次递归都遍历前面所有元素找最小值，那时间复杂度确实是O(n²)，但你的代码是线性递归，每次只和前n-1个元素的最小值做一次比较。
• 错误理解了递归的时间开销：以为递归栈的空间复杂度（O(n)）会影响时间复杂度，但空间和时间是两个不同的指标，递归栈不会让时间变成平方级。

你可以自己测试：当n=100时cnt=101，n=200时cnt=201，cnt的增长完全和n成正比，这就是O(n)的直观证明。

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