c++ - 寻找最小数的递归算法的大O()

Question

我有以下代码，我被告知 findmin 是 O(n^2)，但我看不到它。

#include <iostream>
#include <cstdlib>
#include <ctime>

int findmin(const int a[], int n);
int cnt = 0;

int main (void)
{
    int num = 100;
    std::srand(std::time(nullptr));

    int arr[num];
    for (int i = 0; i < num; ++i)
        arr[i] = std::rand() % num;

    findmin(arr, num);
    std::cout << cnt;
    return 0;
}

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;
}

在我看来，这个算法会找到最后一个元素，捕获它并从递归中返回，将它与一个元素进行比较并继续，因此在我看来这是 O(2*n)。

换句话说，如果我们有数组 3、5、7、1、2、6，我们递归地往下挖 6。在往上我们发现 2 小于 6，所以我们挖 2。然后我们继续向上并将其与 1 grub 1 进行比较，然后向上，将其与 7、5、3 进行比较。这就是 O(n)。我们正在遍历数组 n 次。如果有人能向我解释一下，我将不胜感激。

这是我的来源https://stackoverflow.com/a/50034011/5550963

Answer 1

O(n) ⊂ O(n^2) ∧ t(n) ∈ O(n) => t(n) ∈ O(n^2)

是的，findmin 是 O(n)，但它因此也是 O(n^2)。