Складність часу рекуррентного відношення - алгоритм, часові складності, рецидиви

Мені потрібно знайти відношення рецидиву:

int search(int[] a, int l, int h, int goal) {
if (low == high) return 0;
int tg = target(a, l, h);
if (goal < target)
return search(a, l, tg-1, goal);
else if (goal > target)
return search(a, tg +1, h, goal);
else
return a[tg];
}

Яким був би початковий спосіб підійти до цього питання? Я не прошу рішення, а лише початковий спосіб його наближення. Дякую!

Відповіді:

Оскільки ви не питаєте про точне рішення(проте, я можу сказати, що якщо ви цього хочете), я дам вам підказку, яка є дуже простим, але не відомим методом підходу до таких проблем.

Найважливіша ідея - змінити свою функцію на функцію, яка має, мабуть, найгіршу складність, але її очікуваний складність можна легко виміряти, давайте назвемо цю модифіковану функцію findTarget2:

public static int findTarget2 (int[] a, int low, int high, int goal) {
if (low == high) return 0;
int len = high - low + 1; //length of the array range, i.e. input size
while (true) {
int target = selectTarget(a, low, high);
if (goal < target && target-low <= 3/4 * len)
return findTarget2(a, low, target-1, goal);
else if (goal > target && high-target <= 3/4 * len)
return findTarget2(a, target+1, high, goal);
else if (goal == target)
return a[target];
}

}

Тепер нехай f(n) бути часовою складністю оригіналу та g(n) бути часовою складністю findTarget2 функція, де n - це розмір їх вводу, тобто довжина діапазону масиву дорівнює high-low+1.

Тепер давайте скажемо це selectTarget призводить до а погане виконання тоді і тільки тоді, коли це не викликає жодного зворотного виклику всередині тіла while.

Перше спостереження полягає в тому g(n) >= f(n), тому що у випадку поганого виконання, findTarget2 в основному викликає себе на одному вході, тоді як вихідна функція зменшує розмір вводу принаймні на 1. Таким чином, якщо має верхню межу для g(n), тоді така ж межа стосується і f(n).

Далі очікувана складність часу g(n) можна записати так:

EX[g(n)] <= EX[g(3/4 * n) + X * O(n)]

що можна записати наступним чином, використовуючи лінійність очікуваного значення:

EX[g(n)] <= EX[g(3/4 * n)] + EX[X] * O(n)

де X є випадковою величиною, що позначає кількість виконань циклу while, доки результатом не буде зворотний виклик, і останнє O(n) - нерекурсивний час, проведений у findTarget2 функція, і це "s O(n), бо так сказано selectTarget функція працює в цей час.

Тепер ваше завдання - просто обчислити EX[X] і тоді ви можете використовувати Майстерна теорема щоб отримати остаточну очікувану часову складність g(n), що також є верхньою межею очікуваної часової складності f(n), отже, верхня межа складності вихідної функції.