समय जटिलता पुनरावृत्ति संबंध - एल्गोरिथ्म, समय-जटिलता, पुनरावृत्ति

मुझे पुनरावृत्ति संबंध खोजने की आवश्यकता है:

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 परिणाम में ए बुरा अमल अगर और केवल अगर यह शरीर के अंदर किसी भी वापसी कॉल का कारण नहीं है।

पहला अवलोकन यह है कि 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 जब तक यह रिटर्न कॉल और अंतिम में परिणाम नहीं देता है तब तक लूप निष्पादन की संख्या को दर्शाता हुआ यादृच्छिक चर है O(n) में गैर-पुनरावर्ती समय व्यतीत होता है findTarget2 समारोह, और यह है O(n), क्योंकि यह कहा जाता है कि selectTarget उस समय में फ़ंक्शन चलता है।

अब आपका काम सिर्फ गणना करना है EX[X] और फिर आप इसका उपयोग कर सकते हैं मास्टर प्रमेय अंतिम अपेक्षित समय जटिलता पाने के लिए g(n), जो अपेक्षित समय जटिलता के लिए एक ऊपरी बाध्य है f(n), इसलिए मूल फ़ंक्शन की जटिलता की ऊपरी सीमा।