किसी भी प्रोग्राम (एल्गोरिदम) का सबसे अच्छा मामला और सबसे खराब केस कैसे निर्धारित करें?

Question

मान लीजिए कि मेरे पास यह प्रोग्राम है, मैं 2 इनपुट सूचियों की तुलना करना चाहता हूं। सरणी ए और सरणी बी मानें। मैं सबसे अच्छा केस और फ़ंक्शन का सबसे खराब केस कैसे निर्धारित करूं?

foreach($array_1 as $k){ 
    if(!in_array($k, $array_2)){ 
     array_push($array_2, $k); 
    } 
} 

सबसे अच्छा मामले और पाश के लिए की सबसे खराब स्थिति क्या है:

यहाँ [php] में अपने कोड है? कुछ explaination शामिल करें, धन्यवाद :)

संपादित:

मेरा लक्ष्य 2 सूचियों आम में 1 तत्व है कि सूचियों में तुलना करने के लिए है के बाद से। मुझे लगता है कि मेरा उपरोक्त कोड गलत है। यहाँ मेरी कोड

foreach($array_1 as $k){ 
    if(in_array($k, $array_2)){ 
     array_push($array_3, $k); 
    } 
} 

की अद्यतन किया जाता है और मुझे लगता है कि यह होगा:

बेस्ट मामले: हे (एन)

सबसे खराब मामला: हे (एन * एम)

Answer 1

लेट्स एक त्वरित विश्लेषण करें:

foreach($array_1 as $k) 

का अर्थ है कि भीतर के ऑपरेशन को सरणी के प्रत्येक तत्व के लिए दोहराया जाएगा। N द्वारा सरणी के आकार को इंगित करने दें।

भीतर आपरेशन:

• in_array
• array_push

array_push, इस प्रकार O(1), निरंतर होने की संभावना है, जबकि:

if (!in_array($k, $array_2)) { 
    array_push($array_2, $k); 
} 

यहाँ 2 संचालन कर रहे हैंarray_2 में एक रैखिक खोज की संभावना है जो array_2 संचालन की लंबाई तक 1 ऑपरेशन (पहले तत्व के रूप में पाया जाएगा) ले जाएगा।

ध्यान दें कि in_array यहाँ केवल चर का प्रतिनिधित्व करते हैं:

• सबसे अच्छा मामले: पहला तुलना में in_array रिटर्न ->array_1 के सभी तत्वों को एक ही हैं, और या तो array_2 खाली था या वे के बराबर हैं अपने पहला तत्व जटिलता O(N) है के बाद से हम array_1
• सबसे खराब स्थिति में N तत्व: हर बार जब हम array_2 के प्रत्येक तत्व की जांच ->array_1 के सभी तत्वों को अलग कर रहे हैं और वे array_2 के पिछले तत्वों से भिन्न हैं।यदि Marray_2 की लंबाई जब यह inputed है, तो जटिलता O(N * (N+M)), (N+M)/2array_2 में खोज के रूप में यह MM+N के तत्वों और निरंतर 2O अंकन
में खारिज किए जाने से बढ़ रहा है के लिए मतलब समय होने के रेखा के साथ है

उम्मीद है कि इससे मदद मिलती है।

Answer 2

आम तौर पर ऐसी समस्या के साथ मैं सिर्फ डॉ एविल के रूप में एल्गोरिदम को देखता हूं और पूछता हूं, "मैं इसे अधिकतर समय कैसे ले सकता हूं?"

Answer 3

बिग ओ नोटेशन अनुमान के बारे में सब कुछ है। यह एल्गोरिदम की तुलना करना आसान बनाता है।

यदि आप तत्वों की अपनी सरणी की कल्पना करते हैं, तो एक खोज ऑर्डर हो सकती है एन (आपको जिस आइटम को आप चाहते हैं उसे ढूंढने के लिए प्रत्येक आइटम को देखना चाहिए), यदि आपके पास आदेशित संग्रह है या यह आदेश हो सकता है तो यह लॉग (एन) हो सकता है अपने संग्रह प्रकार के आधार पर भी आदेश 1 हो।

यहां महत्वपूर्ण बात यह है कि आपके एल्गोरिदम को देखना और यह निर्धारित करना है कि महत्वपूर्ण संचालन क्या हैं।

पूर्वानुमान स्पष्ट रूप से एक आदेश एन ऑपरेशन है, परिभाषा के अनुसार आपको अपनी सूची में प्रत्येक तत्व पर काम करना होगा। ओ (एन)

अगला आपका है अगर इनएरे 2। यह एक सरणी पर एक खोज की तरह लगता है, जो संभवतः अनियंत्रित होगा, इसलिए यह आदेश एन (रैखिक खोज) होगा। तो आपकी जटिलता अब ओ (एन * एम) होगी। (सरणी 1 में प्रत्येक एन तत्वों के लिए, सरणी 2 पर आदेश की जटिलता की खोज करें)।

अंत में आपके पास एक सरणी धक्का है। मैं आपके पर्यावरण को नहीं जानता लेकिन यह ऑर्डर 1 या ऑर्डर एन हो सकता है अगर सरणी को फिर से स्थानांतरित करने की आवश्यकता है और बढ़ने के लिए कॉपी किया गया है। आइए इसे सरल रखने के लिए ऑर्डर 1 मान लें। इसलिए बिग ओ में आपकी जटिलता ओ (एन * एम) है।

तो अब प्रत्येक तत्व के लिए सबसे अच्छा मामला यह है कि पहले प्रयास पर इसके समकक्ष को ढूंढें और सरणी पुश करें, जो ओ (एन * 1 * 1) = ओ (एन) होगा।

सबसे खराब मामला यह है कि प्रत्येक तत्व दूसरी सूची में नहीं पाया जा सकता है जो सरणी 2 में सभी तत्वों की पूरी खोज को मजबूर कर रहा है। इसलिए जटिलता ओ (एन * एम) है।

आपके शिक्षक आपकी सोच को समझना चाहते हैं ताकि उन्हें अपनी धारणाएं दिखाएं। मैं अत्यधिक अनुशंसा करता हूं कि आप यहां दी गई धारणाओं पर भरोसा करने से पहले दिए गए सटीक प्रश्न और जानकारी को पढ़ लें, आपको भाषा/मंच कहा जा सकता है जो आपको प्रत्येक मामले में उपयोग किए जाने वाले सटीक दंड और एल्गोरिदम बताएगा। उम्मीद है कि मदद करता है :)