Relacja częstości powikłań czasowych - algorytm, złożoność czasowa, powtarzalność

Muszę znaleźć relację powtarzania:

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];
}

Jaki byłby początkowy sposób podejścia do tego pytania? Nie pytam o rozwiązanie, ale tylko o wstępny sposób podejścia. Dzięki!

Odpowiedzi:

Ponieważ nie pytasz o dokładne rozwiązanie(jednak mogę to zapewnić, jeśli chcesz), dam ci podpowiedź, która jest bardzo prostą, ale nie znaną metodą zbliżania się do takich problemów.

Kluczową ideą jest zmodyfikowanie funkcji do funkcji, która ma prawdopodobnie najgorszą złożoność, ale jej spodziewany złożoność można łatwo zmierzyć, nazwijmy tę zmodyfikowaną funkcję 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];
}

}

Teraz pozwól f(n) być złożonością czasową oryginału i g(n) być złożonością czasu findTarget2 funkcja, gdzie n jest wielkością ich wejścia, tzn. równą długości zakresu macierzy high-low+1.

Powiedzmy to selectTarget wyniki w złe wykonanie jeśli i tylko wtedy, gdy nie spowoduje to żadnego wywołania zwrotnego w ciele.

Pierwsza obserwacja jest taka g(n) >= f(n), ponieważ w przypadku złej egzekucji findTarget2 zasadniczo wywołuje się na tym samym wejściu, podczas gdy oryginalna funkcja zmniejsza rozmiar wejścia o co najmniej 1. Zatem jeśli ma górną granicę dla g(n), wtedy obowiązuje ta sama granica f(n).

Następnie oczekiwana złożoność czasu g(n) można napisać w następujący sposób:

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

które można zapisać w następujący sposób, używając liniowości oczekiwanej wartości:

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

gdzie X jest zmienną losową oznaczającą liczbę wykonań pętli, dopóki nie zakończy się wywołaniem zwrotnym i ostatnim O(n) jest nierekurencyjnym czasem spędzonym w findTarget2 funkcja i to jest O(n), ponieważ tak się mówi selectTarget funkcja działa w tym czasie.

Teraz twoim zadaniem jest tylko obliczenie EX[X] a następnie możesz użyć Twierdzenie mistrza aby uzyskać ostateczną oczekiwaną złożoność czasu g(n), który jest również górną granicą dla oczekiwanej złożoności czasu f(n), więc górna granica złożoności pierwotnej funkcji.