एल्गोरिदम की जटिलता को जानें

यह लेख कंप्यूटर विज्ञान में उपयोग किए जाने वाले अधिकांश एल्गोरिदम के रनटाइम और मेमोरी उपयोग के बारे में बात करता है। अतीत में, जब मैं एक साक्षात्कार की तैयारी कर रहा था, तो मैंने इंटरनेट पर शोध करने के लिए खोज और सॉर्टिंग एल्गोरिदम के सबसे अच्छे, औसत और सबसे खराब मामले के बारे में जानकारी प्राप्त करने में बहुत समय बिताया ताकि साक्षात्कार में पूछे गए प्रश्न मुझे चकरा न दें। पिछले कुछ वर्षों में, मुझे सिलिकॉन वैली के कई स्टार्टअप्स के साथ-साथ याहू, ईबे, लिंक्डइन और गूगल जैसी कई बड़ी कंपनियों में साक्षात्कार दिया गया है, और हर बार जब मैं साक्षात्कार के लिए तैयार हुआ, तो मैंने सोचा: "क्यों किसी ने भी एक अच्छा धोखा पत्र नहीं बनाया। एल्गोरिदम की असममित जटिलता? "। आपके समय को बचाने के लिए, मैंने ऐसी चीट शीट बनाई। इसका आनंद लें!

खोज

छंटाई

डेटा संरचनाएं

ढेर

ग्राफ दृश्य

चलो एक ग्राफ के साथ | V | कोने और | ई | पसलियों तो

स्पर्शोन्मुख वृद्धि संकेतन

1. (O - बड़ा) ऊपरी बाउंड है, जबकि (ओमेगा - लार्ज) निचला बाउंड है। थीटा को दोनों (ओ - बड़े) और (ओमेगा - बड़े) की आवश्यकता होती है, इसलिए यह एक सटीक अनुमान है (यह ऊपर और नीचे दोनों से सीमित होना चाहिए)। उदाहरण के लिए, Ω (n logn) की आवश्यकता वाले एल्गोरिथ्म को कम से कम n logn समय की आवश्यकता होती है, लेकिन ऊपरी सीमा ज्ञात नहीं है। एक एल्गोरिथ्म की आवश्यकता algorithm (एन लोगन) बेहतर है क्योंकि इसमें कम से कम एन लोगन (iring (एन लोगन)) की आवश्यकता होती है और एन लोगन (ओ (एन लोगन)) से अधिक नहीं।
2. f (x) = Θ (g (n)) का अर्थ है कि f, g की तरह बढ़ता है जब n अनंत तक जाता है। दूसरे शब्दों में, विकास दर f (x) विकास दर g (n) के समानुपातिक रूप से आनुपातिक है।
3. f (x) = O (g (n))। यहाँ विकास दर g (n) से तेज नहीं है। ओ लार्ज सबसे अधिक उपयोगी है क्योंकि यह सबसे खराब स्थिति का प्रतिनिधित्व करता है।

संक्षेप में, यदि एक एल्गोरिथ्म में जटिलता __ है तो इसकी दक्षता __ है

ओ वृद्धि चार्ट - बड़ा