इनपुट के साथ एल्गोरिदम जटिलता फिक्स्ड साइज्ड

Question

मुझे बड़े ओ नोटेशन के बारे में कुछ संदर्भ मिले, लेकिन जहां तक ​​मैं एल्गोरिदम जटिलता को समझ सकता हूं इनपुट डेटा के आकार का एक कार्य है।

उदाहरण के लिए, यदि बबल प्रकार की जटिलता O(n^2) है, n इनपुट सरणी का आकार है। सही?

लेकिन, मैं एल्गोरिदम की जटिलता को कैसे निर्धारित कर सकता हूं जिसने इनपुट आकार तय किया है और इनपुट के मानों पर निर्भर करता है। उदाहरण के लिए, सबसे बड़ा आम भाजक (GCD) की खोज इस प्रकार दिखाई देगा:

def GCD(x, y): 
    while x != y: 
     if x < y: 
      x, y = y - x, x 
     else: 
      x, y = x - y, x 
    return x 

इस एल्गोरिथ्म की जटिलता क्या है? और यह कैसे निर्धारित किया जाता है?

संपादित करें: फ़ंक्शन का परिवर्तित नाम और एल्गोरिदम का सही नाम। श्रीवत्सआर, इसे इंगित करने के लिए धन्यवाद।

Answer 1

लोग बड़े-छोटे ओ ओशन के साथ थोड़ा तेज़ और ढीला खेलते हैं। GCD के मामले में, वे आम तौर पर यह 2 तरीकों से कार्य करें:

1) आप सही, एल्गोरिथम जटिलता है, और इसलिए बड़ा-ओ अंकन कर रहे हैं, इनपुट के टुकड़े में आकार की दृष्टि से कहा जाना चाहिए इनपुट के मूल्यों के संदर्भ में नहीं। इस तरह पी, एनपी, और इसी तरह परिभाषित किया गया है। द्विआधारी इनपुट और मनमाने ढंग से बड़ी संख्या (जैसे बिग्नम प्रतिनिधित्व), और एन इनपुट की बिट्स की संख्या मानते हुए, आपके जीसीडी में अधिकतम 2^एन घटाव की आवश्यकता होती है, जिनमें से प्रत्येक को समय के प्रत्येक बिंदु पर चलाने के लिए समय (एन) की आवश्यकता होती है संख्या घटाया जा रहा है। तो यह ओ (एन * 2^एन) है। यदि आप घटाव के बजाय विभाजन का उपयोग करते हैं तो जीसीडी निश्चित रूप से बहुत तेज हो सकता है: ओ (एन^2)।

तो, जब हम कहते हैं कि testing primality was proved in 2002 to be done in polynomial time, यह जटिलता की तकनीकी परिभाषा है, और हमारा मतलब है कि अंकों की संख्या (जो मुश्किल हिस्सा है) में बहुपद है, इनपुट संख्या में बहुपद नहीं है (जो करने के लिए तुच्छ आसान है परीक्षण विभाजन का उपयोग कर "उप-रैखिक समय" में)।

लेकिन व्यावहारिक रूप से, एल्गोरिदम के लिए जो पूर्णांक पूर्णांक इनपुट लेता है, जटिलता के बारे में बात करना अधिक सुविधाजनक है जैसे कि इनपुट इनपुट का आकार नहीं था। यह तब तक हानिकारक नहीं है जब तक आप स्पष्ट न हों कि उन मामलों में आपका क्या मतलब है जो संदिग्ध हो सकते हैं।

2) प्रैक्टिस में, पूर्णांक इनपुट अक्सर निश्चित आकार, 32 बिट या जो कुछ भी होते हैं, और उनके जैसे ऑपरेशन, गुणा और विभाजन जैसे ओ (1) समय होते हैं। हम इन तथ्यों का चयन अपने क्रम विश्लेषण में चुनिंदा रूप से करते हैं। तकनीकी रूप से यदि आपका जीसीडी कार्यक्रम केवल इनपुट (2^32-1) तक इनपुट स्वीकार करता है, तो यह ओ (1) है। इसके चलने वाले समय पर इसकी ऊपरी सीमा है। विश्लेषण का अंत

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

यह स्वीकार करना अधिक सुविधाजनक है कि यह जोड़ ओ (1) है क्योंकि संख्या निश्चित आकार के हैं, लेकिन अनदेखा करें कि जीसीडी भी ओ (1) है, यह दिखाता है कि सीमा में इसका व्यवहार [1, 2^32) अनंत तक फैलता है, और उस आधार पर इसका विश्लेषण करता है। फिर एन के साथ दो इनपुट में से अधिकतम, यह ओ (एन): ओ (एन) घटाव आता है, प्रत्येक स्थिर समय लेता है।

फिर, यह जानने के बाद अस्पष्ट नहीं है कि संदर्भ की शर्तें क्या हैं, लेकिन एल्गोरिदम के इस विश्लेषण के विरुद्ध, यू (एन^2) के साथ यूक्लिड के एल्गोरिदम के पहले विश्लेषण की ग़लत तुलना करने से सावधान रहें। घटाव, ओ (एन)। एन प्रत्येक में समान नहीं है, और घटाव तेज़ नहीं है ;-)

Answer 2

इनपुट आकार संख्या x और y के आकार का योग है (उदाहरण के लिए कितने अंक संख्या में हैं)

Answer 3

बिग ओ जटिलता सबसे खराब स्थिति asymptotic क्रम व्यवहार है। यह किसी विशेष एल्गोरिदम में इनपुट आकार (इनपुट की मात्रा) पर निर्भर नहीं है - हालांकि यह अक्सर होता है। दूसरे शब्दों में, यह सीमित कार्य है जो रनटाइम का वर्णन करता है क्योंकि इनपुट को अनंत तक ले जाया जाता है।

आपके मामले में, यदि एक्स या वाई असंबद्ध हैं, तो एसिम्प्टोटिक रनटाइम है। यदि नहीं, तो रन समय के बारे में सोचें यदि x = 1, और y = Int32.Max?

Answer 4

बिग-ओ नोटेशन को निर्दिष्ट किया जाना चाहिए कि क्या मापा जा रहा है।

उदाहरण के लिए, सॉर्ट एल्गोरिदम के लिए बिग-ओ नोटेशन आमतौर पर तुलना की संख्या को मापता है।

आपके जीसीडी उदाहरण को x और y के मानों की तुलना निष्पादित निर्देशों की संख्या के मुकाबले मापा जा सकता है। आइए अधिक बारीकी से देखें:

def GCD(x, y): 
    while x != y:    # 1 
     if x < y:    # 2 
      x, y = y - x, x  # 3 
     else:     # 4 
      x, y = x - y, x  # 5 
    return x     # 6 

अंदर से बाहर से काम करें।

x और y के मानों से कोई फर्क नहीं पड़ता, चरण 3 और 5 हमेशा एक निर्देश लेंगे। इसलिए, if चरण 2 का बयान हमेशा दो निर्देश लेगा।

कठिन सवाल चरण 1 है। प्रत्येक पुनरावृत्ति के साथ, x या y को छोटे मान से कम किया जाएगा। मान लें कि x > y। दो बातों में से एक होगा:

• यदि यह शुरू कर दिया है कि x % y == 0, तो पाश (x/y) - 1 बार निष्पादित किया जाएगा और इस कार्यक्रम बंद हो जाएगा।

• अन्यथा, x(x/y) बार कम हो जाएगा से पहले ही से छोटी y है और कार्यक्रम जारी रहेगा।

आप आसानी से किसी भी x और y के लिए निर्देश की संख्या का आकलन कर सकते हैं।आप आसानी से यह दिखा सकते हैं कि किसी दिए गए नंबर z के लिए, आपको z - 1 घटावों की आवश्यकता नहीं होगी - या 2 * (z-1) निर्देश। (gcd(z, 1) के बारे में सोचें।)