ज्ञात जटिलता की मौजूदा समस्या को कम करके एक नई समस्या की निचली सीमा को साबित करते समय रैखिक समय में कमी पर जोर दिया जाता है। मुझे लगता है कि रैखिक समय से अधिक के लिए (ओमेगा एन ^ 2 कहें जो रैखिक ओमेगा एन से अधिक है) हम दो समस्याओं की तुलना नहीं कर सकते हैं। लेकिन इसे औपचारिक रूप से कैसे कहें।

इसके अलावा, ज्ञात समस्या ओमेगा एन ^ 3 कहें। क्या अब ओमेगा n^2 की कमी सुरक्षित रूप से साबित करेगी कि अज्ञात समस्या में n^3 जटिलता है?

0
rajesh 14 मार्च 2020, 22:19

1 उत्तर

सबसे बढ़िया उत्तर

यहाँ एक औपचारिक बयान है।

मान लीजिए कि समस्या प्रकार A को समय O(f(n) में हल किया जा सकता है।

मान लीजिए कि समस्या B को समय O(g(n)) में घटाकर h(n) आकार की समस्या में बदल दिया जा सकता है।

तब हम समस्या B को समय O(g(n) + f(h(n))) में हल कर सकते हैं।

आदर्श रूप से हम चाहते हैं कि कमी तेजी से हो और समस्या बहुत अधिक न बढ़े। आप आम तौर पर एक रेखीय समय में कमी से बेहतर नहीं कर सकते क्योंकि यह केवल समस्या में प्रवेश करने के लिए रैखिक समय लेता है। इसलिए वही आदर्श है।

ध्यान दें कि यदि f(n) में एक बहुपद ऊपरी सीमा है तो "आकार की समस्या h(n)" को "आकार की समस्या O(h(n))" में शिथिल किया जा सकता है। यह अक्सर सच होता है, और बहुत प्रयास बचाता है। हालांकि एक उदाहरण जहां उस तरह का सरलीकरण विफल रहता है f(n) = 2^n और h(n) = n+log(n)) के साथ है।

1
btilly 14 मार्च 2020, 22:42