जावा टाइम कॉम्प्लेक्सिटी ओ (एन^2/3)

Question

मेरी गणित पृष्ठभूमि इतनी अच्छी नहीं है, यह जावा इनपुट को विभिन्न इनपुट के रनटाइम अनुपात के साथ लिखने का मेरा प्रयास है।

1. एन^2/3 के साथ। के बाद से n^2/3 = घनमूल n * घनमूल n, इसलिए मैं

   public void test(int n){ 
       for (int i = 0; i*i*i < n; i++) { 
        for (int j = 0; j*j*j < n; j++) { 
         count ++; 
        } 
       } 
   } 
   

2. 4^n के साथ

   लिख सकते हैं। क्या मैं फिबोनासी विधि का उपयोग कर सकता हूं?

   public int fibonnaci(int n) { 
       if (n <= 1) { 
        return 1; 
       } else { 
        return fibonnaci(n - 2) + fibonnaci(n - 1); 
       } 
   } 
   

मैं जान सकती हूँ कि मेरे कोड ऊपर सही है? बहुत धन्यवाद!

Answer 1

क्या आप बस कोई कोड लिख रहे हैं जो उस बड़े-बाध्यता की समय-जटिलता लेता है?

# 1 के लिए था, हाँ, इसमें O(n^(2/3)) लगेगा।

लेकिन # 2 के लिए, आपका कोड O(2^n), और theta(1.6...^n), और 1.6 ले जाएगा .. प्रसिद्ध सुनहरा अनुपात संख्या है।

संदर्भ: Computational complexity of Fibonacci Sequence

Answer 2

पहले एक सही है, और वास्तव में अच्छी तरह सोचा।

---

दूसरा एक नहीं है। फाइबर की गणना करने के लिए उस एल्गोरिदम में ओ (एन^4) (EDIT: की तुलना में बहुत अधिक समय जटिलता है, जब मैंने यह उत्तर लिखा था, तो सवाल पूछा गया था - प्रश्न को अपडेट किया गया है)। यह बहुपद भी नहीं है। तर्क के रूप में इस प्रकार है

• मिथ्या (1):: #fib (1) = 1 (यह सीधे आकर (संकेतन #fib (एक्स): बार मिथ्या की संख्या मिथ्या (एक्स) की गणना करने के कहा जाता है) परिणाम)
• फिब (2): # फिब (2) = 3 (फाइब (2) के लिए एक, जो इसे फाइब (0) और फाइब (1) के लिए कहते हैं)
• फिब (3): #fib (3) = 5 (फाइब (3) के लिए एक, जो इसे फाइब (2) और फाइब (1) के लिए कॉल करता है, 3 + 1 और कॉल देता है)
• फाइब (4): # फिब (4) = 9
• फिब (5): # फिब (5) = 15
• फाइब (6): # फिब (6) = 25
• ...
• मिथ्या (i): #fib (i) = 1 + #fib (i-1) + #fib (i-2)

तो, तुम हो:

• #fib (i) ~ = #fib (i-1) + #fib (i-2)

इस से, यह एक उचित अनुमान है कि गणना के मिथ्या (i) लेता है "के बारे में होगा "(वास्तव में, फाइब (i-1) की गणना करने के लिए 2 बार समय से थोड़ा सा)। इसलिए, आप "अनुमान लगा सकते हैं" कि ओ (# फिब (i)) = ओ (2^i)। यह सही जवाब है, जिसे आप प्रेरण से आसानी से साबित कर सकते हैं।

बस फिबोनासी अनुक्रम के बारे में समाप्त करने के लिए, एन-वें नंबर की गणना करने के लिए बहुत तेज एल्गोरिदम हैं। उदाहरण के लिए, रैखिक समय (यानी, ओ (एन)) के साथ एक एल्गोरिदम आपके द्वारा लिखे गए फ़ंक्शन को याद रखना है (यानी, यह जांचने के लिए मानचित्र से परामर्श लें कि यह एन के परिणाम को जानता है या नहीं, तो इसे तुरंत वापस कर दें, अन्यथा, गणना करें इसे, इसे स्टोर करें और इसे वापस करें)। closed formula to calculate the n-th fib भी है, इसलिए निरंतर समय एल्गोरिदम (यानी, ओ (1))।

---

अंत में, हे का एक उदाहरण (एन^4) एल्गोरिथ्म 4 भीतरी छोरों के साथ कुछ भी, प्रत्येक पाश चल "के बारे में" n गुना है।

उदाहरण के लिए, पक्ष n के एन क्यूब्स की मात्रा (एक गैर इष्टतम तरीके से) की गणना:

int volume = 0; 
for (int cube = 0; cube < n; cube++) 
    for (int x = 0; x < n; x++) 
    for (int y = 0; y < n; y++) 
     for (int z = 0; z < n; z++) 
     volume++; 
return volume; 

Answer 3

यह वास्तव में एक जवाब नहीं है, लेकिन यहां एक "धोखा" समाधान का चित्र है O(F(N)) समय लेने वाले प्रोग्राम का उदाहरण प्रदान करने की समस्या के लिए;

1. एक जावा समारोह वस्तु बना लिए F(N) मूल्यांकन करने के लिए एक N दिया:

---

public void computeOrderFN(int n, FunctionInt2Int fn) { 
     int count = fn.evaluate(n); 
     for (int i = 1; i < count; i++) { 
      // Do something O(1) that the compiler can't optimize away) 
     } 
    } 

---

:

निम्न विधि के लिए एक पैरामीटर के रूप में यह दर्रा

लेकिन इसका उपयोग न करें अगर "स्मार्ट ** एस" होने के लिए क्रेडिट खोने का जोखिम है :-)