मैं समय जटिलता के बारे में कौरसेरा पाठ्यक्रम सीख रहा हूं। मुझे एक वीडियो में इसका सामना करना पड़ा और मुझे लगा कि कुछ गड़बड़ है। “तो मान लीजिए कि हमारे पास एक एल्गोरिथ्म है जिसका रनटाइम लगभग n के समानुपाती है और हम चाहते हैं कि यह इसे एक ऐसी मशीन पर चलाए जो लगभग एक गीगाहर्ट्ज़ पर चलती है। हम कितना बड़ा इनपुट संभाल सकते हैं कि हम गणना को एक सेकंड में पूरा कर लेंगे ? ” (1GHZ सीपीयू (10^9 चक्र प्रति सेकंड))
“ठीक है, अगर यह लगभग n आकार पर चलता है, तो आप लगभग एक अरब आकार के इनपुट को संभाल सकते हैं, इससे पहले कि इसमें एक सेकंड से अधिक समय लगे” (10^9 / 10^9)
“अगर यह एन स्क्वेयर की तरह चलता है, तो यह बहुत खराब है। आप केवल 30,000 आकार के इनपुट को ही संभाल सकते हैं, इससे पहले कि इसमें एक सेकंड से अधिक समय लगे।” n = 30000, (30000)^2/10^9 = 0.9 सेकंड ~ 1 सेकंड
“यदि इनपुट 2 से n आकार के हैं, तो यह अविश्वसनीय रूप से खराब है, आप एक सेकंड में केवल 30 आकार के इनपुट को ही संभाल सकते हैं” 2^30/10^9 ~ 1.07 सेकंड
एन लॉग (एन) जटिलता के साथ, यदि इनपुट आकार एन 10^9 है, तो इसमें 10^9 * लॉग(10^9) / 10^9 = 9 सेकंड लगना चाहिए, है ना? किसी तरह यह वीडियो में 30 सेकंड दिखाता है। इसमें यह भी कहा गया है कि यदि n = 10^7.5 है तो रनटाइम 1 सेकंड है, जो कि मेरी गणना के साथ भी गलत है।
मैंने प्रत्येक मामले की गणना n, n^2, 2^n जटिलता के साथ की और सब कुछ सही था, केवल nlog(n) मामला गड़बड़ हो गया
अधिक जानकारी के लिए यहां फोटो है: https://i.upanh.org/2022/04/11/nlogn.jpg[^]
पाठ्यक्रम वीडियो लिंक किया गया (3:40 से 5:00 भाग है): https://www.coursera.org/lecture/algorithmic-toolbox/asympttic-notation-zI8dH[^]
मैंने प्रश्न को संपादित किया ताकि यह बिल्कुल मेरे द्वारा देखे गए पाठ्यक्रम वीडियो जैसा हो जाए
मैंने क्या प्रयास किया है:
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
समाधान 1
उद्धरण:यदि इनपुट आकार n 10^9 है, तो इसमें 10^9 * लॉग(10^9)/10^9 = 9 सेकंड लगने चाहिए, है ना?
नहीं ! आप बिग ओ नोटेशन से रनटाइम की गणना नहीं करते हैं, कम से कम अकेले तो नहीं।
बिग ओ नोटेशन आपको एल्गोरिदम की श्रेणी जटिलता बताता है, रनटाइम नहीं, सीधे नहीं।
जब आपके पास दिए गए डेटा आकार के लिए रनटाइम होता है, तो बिग ओ जटिलता आपको किसी अन्य डेटा आकार के लिए रनटाइम का मूल्यांकन करने की अनुमति देती है।
20 से 10^6 तक डेटा के लिए आपके 1 सेकंड के समय का मतलब है कि आपको सार्थक समय प्राप्त करने के लिए मिलीसेकंड समय पर स्विच करने की आवश्यकता है।
समाधान 2
बड़ा O निष्पादन का सटीक समय नहीं बताता। उदाहरण के लिए देखें बिग ओ नोटेशन – विकिपीडिया[^] (गुण अनुभाग, एक स्थिरांक से गुणा).
समाधान 3
दूसरे जो कहते हैं, उसमें जोड़ने के लिए, आप किसी भी तरह से घड़ी चक्र को सीधे निष्पादन समय के साथ बराबर नहीं कर सकते हैं – कुछ मशीन संचालन को निष्पादित करने के लिए n चक्र लगते हैं, अन्य n * 2 हो सकते हैं। इसमें जोड़ने के लिए, आधुनिक प्रोसेसर पाइपलाइन किए गए हैं – इसलिए कुछ निर्देश प्रारंभ हो सकता है जबकि अन्य निष्पादित, कैश्ड हैं – इसलिए निष्पादन का समय इस बात पर निर्भर हो सकता है कि किसी निर्देश को अंतिम बार कितने समय पहले निष्पादित किया गया था और यदि इसका डेटा L1, L2 या L3 कैश में उपलब्ध है, निष्पादित करने के लिए मुफ्त कोर की उपलब्धता, साथ ही कई अन्य विवरण।
आप केवल यह नहीं कह सकते कि “मेरी घड़ी की गति X है, इसलिए मेरा निष्पादन समय X * Y है” – ऐसे कई अन्य कारक हैं जो इसे प्रभावित करेंगे।
समाधान 5
यदि यह लॉग है तो 30 सेकंड लगभग सही है2(एन)। लकड़ी का लट्ठा2(1000) ~=10.
संपादन करना: O(n log(n)) एल्गोरिदम अक्सर समस्या को पुनरावर्ती रूप से आधे में विभाजित करते हैं, प्रत्येक भाग को अलग से हल करते हैं, और फिर समाधानों को जोड़ते हैं। यही कारण है कि लॉग इन करें2 आमतौर पर निहित है. मर्जसॉर्ट एक अच्छा उदाहरण है।
समाधान 6
बड़ा O नोटेशन आपको केवल यह बताता है कि निष्पादन समय कैसा होगा परिवर्तन जब समस्या का “आकार” बदल दिया जाता है, तो यह किसी विशिष्ट मामले के लिए वास्तविक अनुमान प्रदान नहीं करता है।
दूसरे शब्दों में, उदाहरण के लिए, कोई अज्ञात कारक है O(n2) मतलब हो सकता है
time_needed = constant * n * n
जहां कोई भी यह नहीं बता रहा है कि स्थिरांक का मान क्या है, इसलिए time_needed के लिए कोई ठोस मान नहीं है।
उदाहरण आपको केवल यह बताता है कि दोगुनी बड़ी समस्या को हल होने में चार गुना अधिक समय लगेगा।
コメント