बिग के उदाहरण 2 हे^n

Question

तो मैं चित्र कर सकते हैं क्या एक एल्गोरिथ्म है कि n^ग की जटिलता, बस छोरों के लिए नेस्ट की संख्या है।

for (var i = 0; i < dataset.len; i++ { 
    for (var j = 0; j < dataset.len; j++) { 
     //do stuff with i and j 
    } 
} 

लॉग कुछ है कि डेटा आधा हर बार में सेट विभाजन है, द्विआधारी खोज इस (पूरी तरह यकीन नहीं इस के लिए क्या कोड की तरह दिखता है) करता है।

लेकिन क्या एक एल्गोरिथ्म का एक सरल उदाहरण है कि ग^n या अधिक विशेष रूप 2^n है। क्या ओ (2^एन) डेटा के माध्यम से लूप पर आधारित है? या डेटा कैसे विभाजित है? या पूरी तरह से कुछ और?

Answer 1

एल्गोरिदम अक्सर पुनरावर्ती एल्गोरिदम कि रिकर्सिवली आकार N-1 के दो छोटे समस्याओं को सुलझाने के द्वारा आकार एन की एक समस्या का समाधान कर रहे हैं।

इस कार्यक्रम, उदाहरण के सभी छद्म कोड

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg) 
{ 
    if (N<1) { 
     return; 
    } 
    if (N>1) { 
     solve_hanoi(N-1, from_peg, spare_peg, to_peg); 
    } 
    print "move from " + from_peg + " to " + to_peg; 
    if (N>1) { 
     solve_hanoi(N-1, spare_peg, to_peg, from_peg); 
    } 
} 

Let टी (एन) समय इसके लिए लेता हो में एन डिस्क के लिए समस्या प्रसिद्ध "हनोई के टावर्स" हल करने के लिए आवश्यक चाल बाहर प्रिंट के लिए एन डिस्क

हम:

T(1) = O(1) 
and 
T(N) = O(1) + 2*T(N-1) when N>1 

आप बार-बार पिछले अवधि का विस्तार करते हैं, तो आपको मिलेगा:

T(N) = 3*O(1) + 4*T(N-2) 
T(N) = 7*O(1) + 8*T(N-3) 
... 
T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1) 
T(N) = (2^N - 1)*O(1) 
T(N) = O(2^N) 

वास्तव में यह पता लगा लिए, आपको सिर्फ इतना पता है कि पुनरावृत्ति संबंध में कुछ पैटर्न घातीय परिणामों के लिए नेतृत्व। आम तौर पर T(N) = ... + C*T(N-1)C > 1 के साथ ओ (x^N) का अर्थ है। देखें:

https://en.wikipedia.org/wiki/Recurrence_relation

Answer 2

उदा। के बारे में सोचें एक सेट के सभी संभावित सबसेट पर पुनरावृत्त। उदाहरण के लिए इस प्रकार के एल्गोरिदम का उपयोग सामान्यीकृत knapsack समस्या के लिए किया जाता है।

यदि आपको यह समझना मुश्किल लगता है कि सबसेट्स पर पुनरावृत्ति कैसे ओ (2^एन) में अनुवाद करता है, तो एन स्विच का एक सेट कल्पना करें, उनमें से प्रत्येक सेट के एक तत्व से संबंधित है। अब, प्रत्येक स्विच चालू या बंद किया जा सकता है। सबसेट में होने पर "चालू" के बारे में सोचें। नोट, कितने संयोजन संभव हैं: 2^एन।

आप कोड में एक उदाहरण देखने के लिए चाहते हैं, यह आम तौर पर आसान प्रत्यावर्तन के बारे में सोचने के लिए यहाँ है, लेकिन मैं किसी भी अन्य अच्छा और understable उदाहरण आयुध डिपो सोच भी नहीं सकते अभी।

Answer 3

int Fibonacci(int number) 
{ 
    if (number <= 1) return number; 

    return Fibonacci(number - 2) + Fibonacci(number - 1); 
} 

इनपुट डेटा सेट में प्रत्येक additon के साथ विकास युगल। ओ (2 एन) फ़ंक्शन का विकास वक्र घातीय है - बहुत उथले से शुरू होता है, फिर उल्का बढ़ रहा है। बड़ा हे (2^n), लेकिन काफी बेहतर मेरे उदाहरण यह है:

public void solve(int n, String start, String auxiliary, String end) { 
    if (n == 1) { 
     System.out.println(start + " -> " + end); 
    } else { 
     solve(n - 1, start, end, auxiliary); 
     System.out.println(start + " -> " + end); 
     solve(n - 1, auxiliary, start, end); 
    } 

इस विधि कार्यक्रम प्रिंट में समस्या "हनोई के टावर" हल करने के लिए सभी कदम। दोनों उदाहरण समस्या हल करने के लिए रिकर्सिव का उपयोग कर रहे हैं और बड़े ओ (2^एन) चलने का समय था। समय ओ (2^N) चल साथ

Answer 4

ग^एन = n तत्वों के सभी संयोजन एक c आकार वर्णमाला से।

अधिक विशेष रूप से 2^एन एन बिट्स के साथ सभी संख्याओं का प्रतिनिधित्व करने योग्य है।

आम मामलों रिकर्सिवली लागू किया जाता है, कुछ की तरह:

vector<int> bits; 
int N 
void find_solution(int pos) { 
    if (pos == N) { 
    check_solution(); 
    return; 
    } 
    bits[pos] = 0; 
    find_solution(pos + 1); 
    bits[pos] = 1; 
    find_solution(pos + 1); 
}