क्या ओ (एन * एन) ओ (एन)

Question

से तेज हो सकता है क्या कोई मुझे यथार्थवादी उदाहरण दे सकता है जिसमें O(N*N) एल्गोरिदम O(N) एल्गोरिदम से N>10 के लिए तेज है।

संपादित करें: मुझे यह सवाल बहुत सामान्य होने के लिए पकड़ा जा रहा है। लेकिन मेरे पास केवल एक सामान्य प्रश्न है। ऐसा कोई दूसरा तरीका नहीं है कि इस सवाल से अलग तरीके से पूछा जा सके।

Answer 1

यह किया जा सकता है कि कुछ एक हे (एन * एन) एल्गोरिथ्म तेजी से (डेटा के कुछ शर्त शुरू करने से जैसे) करने की कोशिश की और कुछ इस तरह के साथ समाप्त होता है:

हे (एन):

for (int i=0;i<N;i++){ 
    // do some expensive preconditioning of your data 
    // to enable using O(N) algorithm 
} 
for (int i=0;i<N;i++){ 
    // run the actual O(N) algorithm 
} 

हे (एन * एन):

for (int i=0;i<N;i++){ 
    for (int j=0;j<N;j++){ 
     // run the O(N*N) algorithm 
    } 
} 

बड़ा हे अंकन बड़े एन के लिए ही सीमित व्यवहार निरंतर (या रैखिक) भाग एक बहुत अलग हो सकता है कर रहा है। उदाहरण के लिए यह हो सकता है कि

O(N) =   N + 10000 
O(N*N) = N^2 + 0.5*N + 10 

Answer 2

इनपुट एक पूर्णांक एन है।

पहला उदाहरण: लघु कार्यक्रमों की एक जोड़ी इस तथ्य का उपयोग करती है कि ओ नोटेशन ऊपरी बाउंड है, इसलिए ओ (1) वाला एक प्रोग्राम ओ (एन) और ओ (एन^2), आदि है। ।

कार्यक्रम 1:

def prog1(n) 
    1.upto(n) do |i| 
    end 
end 

कार्यक्रम 2:

def prog2(n) 
    return 
end 

कार्यक्रम 1 हे (एन) और कार्यक्रम है 2 हे है (एन * एन) के साथ-साथ हे (एन) और ओ (1) और ओ (एन^एन^एन^एन^एन)।

फिर भी कार्यक्रम 2 कार्यक्रम की तुलना में तेजी है 1.

दूसरा उदाहरण: प्रोग्राम हैं जो तथ्य यह है कि हे संकेतन n बड़ा हो जाता है के रूप में व्यवहार पर निर्भर करता है का उपयोग की एक जोड़ी।

कार्यक्रम 1:

def prog2(n) 
    if n < 10^100 
     return 
    else 
     1.upto(n) do |i| 
      1.upto(n) do |j| 
      end 
     end 
    end 
end 

कार्यक्रम 1 है हे (एन) और कार्यक्रम 2 हे है (एन * एन): के रूप में

से पहले

कार्यक्रम 2 एक ही।

फिर भी प्रोग्राम 2 प्रोग्राम से तेज़ है> = 10^100 तक।

Answer 3

किसी ने मुझसे एक यथार्थवादी उदाहरण है जिसमें एक हे (एन * एन) एल्गोरिथ्म कुछ एन> 10 के लिए एक हे (एन) कलन विधि की तुलना में तेजी है दे सकते हैं।

बड़ा ओ नोटेशन केवल एल्गोरिदम के एसिम्प्टोटिक प्रदर्शन का वर्णन करता है, एन सकारात्मक सकारात्मक की ओर झुकता है।

और सबसे महत्वपूर्ण बात यह है कि यह एल्गोरिदम के सैद्धांतिक प्रदर्शन का वर्णन करता है - इसके व्यावहारिक कार्यान्वयन की नहीं!

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

सरल उदाहरण। qsort() फ़ंक्शन के अंदर sleep(60) रखो। Asymptotically एल्गोरिदम अभी भी एक ही O(N*log(N)) एल्गोरिदम है, क्योंकि निरंतर 60 दूसरी नींद अनंतता की तुलना में कम है। लेकिन व्यावहारिक रूप से, qsort() कार्यान्वयन किसी भी बबल प्रकार के कार्यान्वयन (sleep() के बिना) से बाहर हो जाएगा, क्योंकि अब N*log(N) के सामने विशाल स्थिर है।

Answer 4

यथार्थवादी उदाहरण के रूप में, my answer से this question देखें।

एन संख्या के माध्य हे (एन) समय में पाया जा सकता है (या तो सबसे खराब स्थिति में, या औसत पर)। उदाहरण के लिए, इस तरह के एक एल्गोरिदम std::nth_element में लागू किया गया है।

हालांकि, छोटे एन एक प्रस्तावित एल्गोरिथ्म के साथ हे (एन^2) के लिए जटिलता तेजी से चला सकते हैं, क्योंकि 1) यह कोई शाखाएं हैं, 2) यह SSE साथ vectorized जा सकता है। कम से कम, एन = 23short प्रकार के तत्वों के लिए, यह 4-5 बार में std::nth_element से बेहतर प्रदर्शन करता है। इस विशेष सेटिंग में छवि प्रसंस्करण में इसका आवेदन है।

पीएस वैसे, std::nth_element के कार्यान्वयन आमतौर पर एन < = 32, जो ओ (एन^2) एल्गोरिदम भी है, आंतरिक रूप से सम्मिलन प्रकार का उपयोग करते हैं।