В худшем случае сложность времени следующей функции? - PullRequest
Новая
       6

В худшем случае сложность времени следующей функции?

0 голосов
/ 23 января 2019
  • V отсортировано
  • Vsize () = N
  • Функция изначально называется searchNumOccurrence (V, k, 0, N-1) 
    int searchNumOccurrence(vector<int> &V, int k, int start, int end) {
    if (start > end) return 0;
    int mid = (start + end) / 2;
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end);
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1);
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);
}

Может кто-нибудь помочь мне с этим вопросом?

Заранее спасибо за объяснение.

Ответы [ 2 ]

0 голосов
/ 23 января 2019

Чем больше у вас одинаковых элементов, тем меньше времени нужно для их поиска с помощью бинарного поиска.Самый медленный первый поиск будет происходить, когда есть только один элемент, который вы ищете log (n). В других случаях поиск первого элемента будет происходить в чем-то похожем на log (n / log (repsOfK)). Но чем больше элементов вы ищетевам нужно будет запускать функцию больше раз, так что это будет сумма O (n) = Log (n / log (repsOfK)) + 2 * log (n / (2 * log (repsOfK-1)) + ... +2 ^ n log (n / (2 ^ n log (repsOfK-2 ^ (n-1))))

Вы должны найти максимум этой функции, чтобы выяснить,ваш ответ

0 голосов
/ 23 января 2019

О чем подумать - представьте, что ваш вектор содержит n копий одной и той же вещи. В этом случае функция будет разбивать массив пополам и искать в обеих половинах, чтобы подсчитать, сколько там копий. И при этом он будет посещать каждый элемент массива хотя бы один раз (проверьте это - понимаете ли вы почему?). Таким образом, в этом случае вы выполняете постоянный объем работы для каждого элемента. Исходя из этого, как вы думаете, что сложность во время выполнения?

...