क्या यह एल्गोरिदम ओ (एन) में चलाएगा?

Question

नोट: यह कोडिंग साक्षात्कार क्रैकिंग 5 वें संस्करण से समस्या 4.3 है

समस्या: एक हल कर (बढते क्रम) को देखते हुए सरणी, एक एल्गोरिथ्म लिखना कम से कम ऊंचाई के साथ एक द्विआधारी खोज वृक्ष बनाने के लिए

यहाँ मेरी एल्गोरिथ्म, जावा में लिखा इस समस्या

public static IntTreeNode createBST(int[] array) { 
     return createBST(array, 0, array.length-1); 
    } 
    private static IntTreeNode createBST(int[] array, int left, int right) { 
     if(right >= left) { 
      int middle = array[(left + right)/2; 
      IntTreeNode root = new IntTreeNode(middle); 
      root.left = createBST(array, left, middle - 1); 
      root.right = createBST(array, middle + 1, right); 
      return root; 
     } else { 
      return null; 
     } 
    } 

मैं लेखक का के खिलाफ इस कोड की जाँच की क्या करना है और यह लगभग समान है।
हालांकि मुझे इस एल्गोरिदम की समय जटिलता का विश्लेषण करने में कठिनाई हो रही है।
मुझे पता है कि यह ओ (लॉग इन)Binary Search जैसा नहीं होगा क्योंकि आप रिकर्सन के प्रत्येक स्तर पर समान मात्रा में काम नहीं कर रहे हैं। पहले स्तर पर ईजी, काम की 1 इकाई, द्वितीय स्तर - 2 इकाइयों की काम, तीसरी स्तर - काम की 4 इकाइयां, (एन) स्तर - एन काम की इकाइयों को लॉग करने के सभी तरीके।

तो बंद आधारित है कि, चरणों की संख्या इस एल्गोरिदम लेता ऊपरी इस गणितीय अभिव्यक्ति से घिरा हो जाएगा

जो Infinite geometric series देखने के बाद, मैं

या 2n के लिए मूल्यांकन जो ओ (एन)

क्या आप लोग मेरे साथ सहमत होंगे यहां काम करें और यह एल्गोरिदम ओ (एन) में चलाएगा या क्या मुझे कुछ याद आया या वास्तव में यह ओ (nlogn) या कुछ अन्य फ़ंक्शन क्लास में चलता है?

Answer 1

कभी-कभी आप पुनरावृत्ति संबंधों को हल करने के बजाय परिणाम में प्रति आइटम की मात्रा की गणना करके गणना को सरल बना सकते हैं। वह चाल यहां लागू होती है। इस स्पष्ट रूप से बराबर फार्म के लिए कोड को बदलने के द्वारा शुरू करें:

private static IntTreeNode createBST(int[] array, int left, int right) { 
    int middle = array[(left + right)/2; 
    IntTreeNode root = new IntTreeNode(middle); 
    if (middle - 1 >= left) { 
     root.left = createBST(array, left, middle - 1); 
    } 
    if (right >= middle + 1) { 
     root.right = createBST(array, middle + 1, right); 
    } 
    return root; 
} 

अब createBST के लिए हर कॉल सीधे 1 नोड पैदा करता है। चूंकि अंतिम पेड़ में एन नोड्स हैं, ncreateBST पर कुल कॉल होना चाहिए और चूंकि प्रत्येक कॉल सीधे निरंतर काम करता है, समग्र समय जटिलता ओ (एन) है।

Answer 2

यदि आप रिकर्सन में भ्रमित हो जाते हैं, तो एक लूप के रूप में रिकर्सिव कॉल (मानसिक रूप से, ज़ाहिर है) को प्रतिस्थापित करें। उदाहरण के लिए, आपके उपरोक्त फ़ंक्शन में, आप "लूप" के अंदर रिकर्सिव कॉल की कल्पना कर सकते हैं। चूंकि, अब यह समय थोड़ी देर तक निष्पादित है जब तक कि सभी एन नोड्स को पार नहीं किया जाता है, जटिलता ओ (एन) होती है।