Подсчет количества вхождений элемента в массиве, используя рекурсию

Question

Я дал следующий запрос:

Создать рекурсивную функцию, которая подсчитывает количество раз v происходит в массиве A путем деления A в два подмассива каждый раз.

Какой лучший способ приблизиться к этому, чем использовать BinarySearch? Я создал следующую функцию:

int count(int *A, int low, int high, int v) { if(low > high) return 0; int total = 0, mid = (low + high)/2; if(A[mid] == v) total++; return count(A, low, mid - 1, v) + total + count(A, mid + 1, high, v); }

Это работает, так что я не нужна проверка на этой части.

Нам не сообщается, отсортирован ли массив A, поэтому необходимо искать как левую половину, так и правую половину массива A. Но мне нужно найти временную сложность функции, которую я написал. Вот что я подумал:

Любые переменные назначения - O(1), поэтому нам нужно рассмотреть только те части, которые нам нужно рассмотреть: count(A, low, mid - 1, v) + total + count(A, mid + 1, high, v). Так как мы разделив массив в 2 части с размером подзадачи 2, я создал следующее рекуррентное соотношение:

T(n) = T(n/2) + O(1) + T(n/2) = 2T(n/2) + O(1),

который мы можем использовать мастер теорему, чтобы дать нам T(n) = O(n). Мой вопрос: мое предположение, что переменные назначения являются постоянными с O(1) и что каждая часть функции count равна T(n/2)?

Общая сложность времени, которую мы получаем от O(n), имеет смысл, потому что мы должны проверить все элементы n в массиве.

Answer 1

У вас возникло соблазн написать «Да» в ответ и стремиться к принятому ответу на короткое замыкание!

Но для получения более подробной информации в рамках наиболее часто используемой вычислительной модели при анализе алгоритмов предполагается, что любые операции с использованием бит log(n) выполняются в O(1) времени. Это эффективно означает, что, если ваш массив не является чрезвычайно большим (например, 2^n), или сами значения чрезвычайно велики, вы можете с уверенностью предположить, что все операции могут выполняться в O(1) времени.

Что касается вашего анализа относительно T(n/2), нет ничего другого, кроме да, это правильно, потому что вы просто уменьшаете длину массива в каждом рекурсивном вызове.