2^एन जटिलता एल्गोरिदम

Question

मुझे 2^एन जटिलता के साथ एक एल्गोरिदम लागू करने और परीक्षण करने की आवश्यकता है। मैं थोड़ी देर के लिए एक खोजने की कोशिश कर रहा हूं। यदि कोई तरीका है तो मैं इसे कार्यान्वित करके स्वीकार कर सकता हूं - 2^एन की सटीक जटिलता के साथ यह इष्टतम होगा। अगर कोई किसी स्थान के बारे में जानता है तो मुझे एक उदाहरण मिल सकता है, या मुझे एक को लागू करने में मदद कर सकता है, यह शानदार होगा :-)। मूल संचालन कुछ भी हो सकता है, लेकिन i ++ की तरह एक एकल स्टेटमेंट; सबसे अच्छा होगा।

Answer 1

एन तत्वों के साथ एक सेट के सभी सबसेट जेनरेट करें।

जोड़ा गया। एस = {a0, a1, ..., an-1} के सभी सबसेट जेनरेट करने का सबसे आसान तरीका शायद रैंक और सबसेट के द्विआधारी प्रतिनिधित्व के बीच अनुवाद करना है।

एस = {ए0, ए 1, ए 2} लें।

rank binary subset 
0 000 {} 
1 001 {a0} 
2 010 {a1} 
3 011 {a0, a1} 
4 100 {a2} 
5 101 {a0, a2} 
6 110 {a1, a2} 
7 111 {a0, a1, a2} 

तो, द्विआधारी में 1 का अर्थ है कि संबंधित तत्व सबसेट में है। ए 0 का मतलब है कि तत्व सबसेट में नहीं है।

लेकिन आपको ग्रे कोड भी देखना चाहिए।

Answer 2

शास्त्रीय रिकर्सिव फिबोनाची संख्या गणना ओ (2^एन) है।

unsigned Fib(unsigned n) 
{ 
    if (n <= 1) 
     return n; 
    else 
     return Fib(n - 1) + Fib(n - 2); 
} 

---

ऊपर के बाद से वास्तव में थीटा (फी^n), मैं एक थीटा (2^n) एल्गोरिथ्म जोड़ रहा है कि 2^लौट n है। यिर्मयाह Willcock के लिए धन्यवाद।

unsigned TwoExp(unsigned n) 
{ 
    if (n == 0) 
     return 1; 
    else 
     return TwoExp(n - 1) + TwoExp(n - 1); 
} 

Answer 3

यहां एक है: 2^(2^n) के अंक आउटपुट।

Answer 4

Quantum Bogosort में 2^एन स्पेस जटिलता है।

Answer 5

मैंने समस्या पर पुनर्विचार करने में काफी समय बिताया और एक समाधान पोस्ट करना चाहता हूं जिसके साथ मैं आया हूं। सभी उत्तरों ने इस समाधान के साथ आने की मेरी क्षमता में योगदान दिया, और जो भी चुकाया गया है उसके लिए बहुत आभारी हूं। :-) मुझे एहसास है कि एल्गोरिदम व्यावहारिक रूप से कुछ भी नहीं करता है।

यह जावा में लिखा है
टैब काम करने के लिए
बुनियादी आपरेशन मैं ++ है पाने के लिए प्रतीत नहीं कर सकते हैं;

public class TwoToTheN 
{ 
    private static int twoToTheN = 0; 
    private static int power = 3; 

    public static void main(String[] args) 
    { 
     twoToTheN(power); 
     System.out.println(twoToTheN); 
    } 

    private static void twoToTheN(int n) 
    { 
     if(n == 0) 
     { 
      twoToTheN++; 
      return; 
     } 
     else if(n == 1) 
     { 
      twoToTheN++; 
      twoToTheN++; 
      return; 
     } 
     twoToTheN(n-1); 
     twoToTheN(n-1); 
    } 
}