Как мне оценить сложность (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 наименьший для всего левогои правый подмассив, так что сначала у вас есть 1 сравнение, затем у вас есть 2, затем 4, пока у вас не будет n сравнений.

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