क्या ऐसी कोई चीज़ "ऋणात्मक" बड़ी-जटिलता है?

Question

संभव डुप्लिकेट:
Are there any O(1/n) algorithms?

यह सिर्फ कोई विशेष कारण के लिए मेरे सिर में पॉप, और मुझे लगता है कि यह एक अजीब सवाल है। क्या कोई ज्ञात एल्गोरिदम या समस्याएं हैं जो वास्तव में आसान या तेज अधिक इनपुट के साथ हल करने के लिए प्राप्त करती हैं? मैं अनुमान लगा रहा हूं कि यदि वहां हैं, तो यह उत्परिवर्तन या सॉर्टिंग जैसी चीजों के लिए नहीं होगा, यह निर्णय समस्याओं के लिए होगा। शायद कुछ समस्या है जहां इनपुट का एक टन होने से कुछ तय करना आसान हो जाता है, लेकिन मैं कल्पना नहीं कर सकता कि क्या।

यदि नकारात्मक जटिलता जैसी कोई चीज़ नहीं है, तो क्या कोई प्रमाण है कि ऐसा नहीं हो सकता है? या यह सिर्फ इतना है कि किसी ने इसे अभी तक नहीं पाया है?

Answer 1

कोई भी संभव नहीं है। चूंकि बिग-ओह ऑपरेशन की संख्या का अनुमान लगाने का अनुमान लगाता है, इसलिए एल्गोरिदम अपने डोमेन आकार से संबंधित प्रदर्शन करता है, इसलिए ऑपरेशन की नकारात्मक संख्या का उपयोग करने के रूप में एल्गोरिदम का वर्णन करना समझ में नहीं आता है।

विकिपीडिया article की औपचारिक परिभाषा अनुभाग वास्तव में सकारात्मक वास्तविक संख्याओं के उपयोग के मामले में बिग-ओह नोटेशन को परिभाषित करता है। तो वास्तव में यहां तक ​​कि एक सबूत भी नहीं है क्योंकि बिग-ओह की पूरी अवधारणा औपचारिक परिभाषा के अनुसार ऋणात्मक वास्तविक संख्याओं पर कोई मतलब नहीं है।

संक्षिप्त उत्तर: यह संभव नहीं है क्योंकि परिभाषा कहती है।

Answer 2

वास्तव में नहीं। ओ (1) सबसे अच्छा है जिसके लिए आप उम्मीद कर सकते हैं।

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

Answer 3

अद्यतन बस इसे स्पष्ट करना, मैं प्रश्न के इस हिस्से का जवाब दे रहा हूँ: वहाँ किसी भी ज्ञात एल्गोरिदम या समस्याओं जो वास्तव में आसान या तेज बड़ा इनपुट के साथ हल करने के लिए मिल सकता है?

स्वीकार किए जाते हैं जवाब यहाँ में बताया गया है, वहाँ कोई तेजी से बड़ा इनपुट के साथ काम एल्गोरिदम हैं। Are there any O(1/n) algorithms? sleep(1/n) जैसे एल्गोरिदम भी अपने इनपुट को पढ़ने में समय व्यतीत करना है, इसलिए इसके चलने का समय कम है।

विशेष रूप से, लेखक referes अपेक्षाकृत सरल-स्ट्रिंग खोज एल्गोरिथ्म:
http://en.wikipedia.org/wiki/Horspool

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

Answer 4

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

लेकिन मुझे नहीं लगता कि यह "नकारात्मक जटिलता" के रूप में योग्य है। इस मामले में सबसे तेज़ प्रदर्शन शायद ओ (1) के रूप में गिना जाएगा, सबसे खराब केस प्रदर्शन ओ (एन) होगा, और औसत प्रदर्शन कहीं भी होगा।

यह छँटाई एल्गोरिदम के लिए कुछ हद तक लागू होता है - उनमें से कुछ हे (एन) सबसे अच्छा हालत में जटिलता और हे (एन^2) सबसे ज्यादा मामले जटिलता, डेटा की स्थिति पर निर्भर करता है क्रमबद्ध करना।

मुझे लगता है कि नकारात्मक जटिलता होने के लिए, परिणाम की गणना करने के लिए कहा जाने से पहले एल्गोरिदम को परिणाम वापस करना चाहिए। अर्थात। इसे एक टाइम मशीन से जोड़ा जाना चाहिए और संबंधित "grandfather paradox" से निपटने में सक्षम होना चाहिए।

Answer 5

ऋणात्मक समय में निष्पादित एल्गोरिदम में सोचने के लिए, पीछे की ओर जाने के बारे में सोचने जैसा ही है।

यदि प्रोग्राम 10:30 बजे निष्पादन शुरू होता है और सुबह 11:00 बजे से गुजरने के बिना 10:00 बजे बंद हो जाता है, तो उसने समय = ओ (-1) के साथ निष्पादित किया है।

=]

अब, गणितीय भाग के लिए:

आप कार्यों कि कुछ ही समय में पीछे की ओर पर अमल का एक अनुक्रम (आप कभी पता नहीं ... lol) के साथ नहीं आ सकते हैं, सबूत काफी सरल है:

positiveTime = हे (-1) का अर्थ है:

positiveTime < = ग * -1, किसी भी सी के लिए> 0 और n> N0> 0

"सी> 0" प्रतिबंध पर विचार करें। हमें एक सकारात्मक संख्या नहीं मिली है जो -1 से गुणा होकर परिणामस्वरूप एक और सकारात्मक संख्या होगी। कि लेने के खाते में से, यह परिणाम है:

positiveTime < = negativeNumber, किसी भी n के लिए> N0> 0

कौन सा बस साबित करता है कि आप हे (-1) के साथ एक एल्गोरिथ्म नहीं हो सकता।

Answer 6

खाली एल्गोरिदम के बारे में अन्य प्रश्न के साथ, यह सवाल संभव या असंभव के मामले की बजाय परिभाषा का विषय है। एक निश्चित मॉडल के बारे में सोचना निश्चित रूप से संभव है जिसके लिए एल्गोरिदम ओ (1/एन) समय लेता है। (यह निश्चित रूप से नकारात्मक नहीं है, बल्कि बड़े इनपुट के साथ घट रहा है।) एल्गोरिदम कुछ अन्य उत्तरों में से एक के रूप में sleep(1/n) जैसे कुछ कर सकता है। यह सच है कि लागत मॉडल टूट जाता है क्योंकि एन को अनंतता में भेजा जाता है, लेकिन एन को अनंतता में कभी नहीं भेजा जाता है; वैसे भी हर लागत मॉडल टूट जाता है। यह कहकर कि sleep(1/n) लेता है ओ (1/एन) समय 1 बाइट से 1 गीगाबाइट तक के इनपुट आकार के लिए बहुत उचित हो सकता है। किसी भी समय जटिलता सूत्र लागू होने के लिए यह एक बहुत विस्तृत श्रृंखला है।

दूसरी ओर, समय जटिलता की सबसे सरल, सबसे मानक परिभाषा इकाई समय चरणों का उपयोग करती है। एक सकारात्मक, पूर्णांक-मूल्यवान फ़ंक्शन के लिए असीमोटोटिक्स कम करना असंभव है; यह छोटा हो सकता है ओ (1)।

Answer 7

मुझे नहीं पता कि यह काफी फिट बैठता है लेकिन यह मुझे बिटोरेंट की याद दिलाता है। जितना अधिक लोग फ़ाइल डाउनलोड करते हैं, तेज़ी से यह उन सभी के लिए जाता है