вычисление временной сложности рекурсивного алгоритма

Question

Я пытаюсь понять временную сложность этого алгоритма, но я не знаю, как это сделать. буду рад любой помощи.

`int g(int arr[], int start, int end, int k)
{
if (start > end) return 0;
int mid = (start + end) / 2;
if (arr[mid] < k) return 1 + g(arr, mid + 2, end, k);
if (arr[mid] > k) return 1 + g(arr, start, mid - 1, k);
return g(arr, start, mid - 1, k) + 1 +
g(arr, mid + 1, end, k);
}`

ответ O (n).

Answer 1

Это рекурсия, использующая механизм бинарного поиска. Каждый раз мы проверяем, равно ли arr[mid] значению k; если оно меньше k, то мы ищем правую половину массива (mid+2 должно быть mid+1), если оно больше, то ищем левую половину массива, если оно равно k тогда мы ищем обе половины массива. Поэтому каждый раз, когда мы вызываем рекурсивную функцию, мы используем только половину ввода (половину массива). Таким образом, мы можем написать что-то вроде этого:

Т (п) = 2 * Т (п / 2) + 1

Т (п) = 2 * 2 * Т (п / (2 * 2)) + 1 + 1

... продолжить расширение

Т (п) = 2 ^ к * Т (п / (2 ^ к)) + к

n / (2 ^ k) = 2 ==> k = log (n)

T (n) = 2 ^ (log (n)) * 1 + log (n) = O(n), зная, что 2 ^ log (n) = n с использованием правил журнала.

даже если вы не спрашивали, но сложность пространства составила бы O(log(n)), поскольку максимальная глубина дерева рекурсии была бы log (n).