用于查找最小数量的递归算法的大O（）(Big O() of recursive algorithm for finding minimum number)

 我有以下代码告诉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，递归地我们走下去grub 6.在我们的路上，我们发现2小于6，所以我们grub 2.比起我们去比较它到1 grub 1并上去，比较它到7,5,3。所以这是O（n）。 我们正在经历n次阵列。 如果有人能向我解释这一点，我将非常感激。 
 
 这里是我的源https://stackoverflow.com/a/50034011/5550963 

I have following code I was told findmin is O(n^2), but I cannot see it.
 
#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;
}
 
In my mind this algorithm goes down the last element, grabs it and comes back from recursion, compares it to an element and goes on, thus in my mind this is O(2*n).
 
In another way if we have array 3, 5, 7, 1, 2, 6, recursively we go down and grub 6. On our way up we find that 2 is smaller than 6 so we grub 2. Than we go up and compare it to 1 grub 1 and go up, comparing it to 7, 5, 3. So that is O(n). We are going through array n times. I would really appreciate if somebody can explain this to me.
 
Here is my source https://stackoverflow.com/a/50034011/5550963

原文：https://stackoverflow.com/questions/50047701