c++ - 如何评估代码的复杂性 (Big-O)？

Question

#include <iostream>

int find_smallest(int a[], int l, int r){
    if (l ==r)
        return a[l];
    else if (l+1 == r)
        return ((a[l] < a[r]) ? a[l] : a[r]);
    else {
        int m = (l + r) / 2;
        int d1 = find_smallest(a, l, m);
        int d2 = find_smallest(a, m+1, r);
        return  ((d1 < d2) ? d1 : d2);
    }
}

int main(){
    int a[] = {5,3,2,5,6,7};
    std::cout << find_smallest(a, 0, 5);
}

这是一段寻找数组中最小元素的代码。我采用了一个 6 元素数组只是为了测试目的，但我应该如何分析程序的 Big-O 复杂性？

Answer 1

这实际上是 O(n) - 找出为什么你必须分析你的算法的递归树以及每一步有多少操作。

分析操作次数很简单，简单比较两个项就O(1)，现在我们需要计算递归函数被调用了多少次。

原来这也很简单，你调用find smallest for the entire left and right subarray，所以首先你有1次比较，然后你有2次，然后是4次，直到你有n次比较。

n + n/2 + n/4 ... = 2*n = O(n)