समय जटिलता और चलने के समय के बीच अंतर

Question

बस सोच रहा है कि एक प्रश्न में एल्गोरिदम के चलने के समय के बारे में बात है, क्या इसका मतलब टाइम कॉम्प्लेक्सिटी के समान है या क्या दोनों के बीच कोई अंतर है?

Answer 1

एल्गोरिदम का विश्लेषण करने के लिए इसे निष्पादित करने के लिए संसाधनों की मात्रा (जैसे समय और संग्रहण) निर्धारित करना है। अधिकांश एल्गोरिदम को मनमानी लंबाई के इनपुट के साथ काम करने के लिए डिज़ाइन किया गया है। आम तौर पर efficiency or running time of an algorithm को इनपुट लंबाई से number of steps (time complexity) या स्टोरेज स्थानों (अंतरिक्ष जटिलता) से संबंधित फ़ंक्शन के रूप में बताया जाता है।

Answer 2

रनिंग समय यह है कि प्रोग्राम चलाने में कितना समय लगता है। समय जटिलता चलने वाले समय के असीमित व्यवहार का वर्णन है क्योंकि इनपुट आकार अनंतता तक रहता है।

आप कह सकते हैं कि चलने का समय "ओ (एन^2) या जो भी हो, क्योंकि यह जटिलता वर्गों और बड़े-ओ नोटेशन का वर्णन करने का बेवकूफ तरीका है। वास्तव में चलने का समय एक जटिलता वर्ग नहीं है, यह या तो एक अवधि है, या एक समारोह जो आपको अवधि देता है। "ओ होने के नाते (एन^2)" उस कार्य की गणितीय संपत्ति है, इसकी पूर्ण विशेषता नहीं है। सटीक चलने का समय 2036 * एन^2 + 17453 * एन + 18464 सीपीयू चक्र, या जो भी हो सकता है। ऐसा नहीं है कि आपको अक्सर उस विवरण में इसे जानने की आवश्यकता होती है, और वैसे भी यह वास्तविक इनपुट के साथ-साथ इनपुट के आकार पर भी निर्भर हो सकता है।

Answer 3

समय जटिलता और चलने का समय पूरी तरह से दो अलग-अलग चीजें हैं।

समय जटिलता एल्गोरिदम से संबंधित एक पूर्ण सैद्धांतिक अवधारणा है, जबकि समय चलाना एक कोड चलने का समय होगा, सभी सैद्धांतिक नहीं।

दो एल्गोरिदम में एक ही समय जटिलता हो सकती है, ओ (एन^2) कहें, लेकिन किसी को दूसरे के रूप में दो गुना अधिक समय लग सकता है।

Answer 4

CLRS 2.2 pg. 25

एक विशेष इनपुट पर एक एल्गोरिथ्म का चलने का समय से आदिम संचालन या "चरण" निष्पादित की संख्या है। के लिए यह सुविधाजनक है कि चरण की धारणा को परिभाषित करें ताकि यह मशीन-स्वतंत्र के रूप में संभव हो।

अब Wikipedia

से ... एक एल्गोरिथ्म के समय जटिलता स्ट्रिंग इनपुट का प्रतिनिधित्व करने की लंबाई के एक समारोह के रूप में चलाने के लिए एक एल्गोरिथ्म द्वारा उठाए गए समय की राशि quantifies।

समय जटिलता सामान्यतः प्राथमिक संचालन एल्गोरिथ्म, जहां एक प्राथमिक कार्रवाई करने के लिए समय की एक निश्चित राशि लेता है द्वारा किया जाता की संख्या की गणना का अनुमान है।

ध्यान दें कि दोनों विवरण इनपुट के आकार के रिश्ते को प्राथमिक/प्राथमिक संचालन की संख्या पर जोर देते हैं।

मुझे विश्वास है कि यह दोनों एक ही अवधारणा को संदर्भित करता है।

अभ्यास में हालांकि आप पाएंगे कि एंटरप्राइज शब्दकोष शायद ही कभी अकादमिक शब्दावली से मेल खाता है, उदा।, बहुत से लोग कोड अनुकूलन करने में काम करते हैं लेकिन शायद ही कभी optimization problems हल करते हैं।

Answer 5

"समय चल रहा है" पर विचार किया जा एल्गोरिथ्म को दर्शाता है:

एक और एल्गोरिथ्म एक ही समस्या का समाधान asymptotically तेजी से, कि है, कम चल रहा है समय के साथ कर सकता है।

दूसरी ओर "समय जटिलता" समस्या के अंतर्गत निहित है। इसे किसी भी एल्गोरिदम हल करने की समस्या के कम से कम चल रहे समय के रूप में परिभाषित किया गया है।

ही distincting जैसे स्मृति, #processors, संचार मात्रा आदि के रूप में एल्गोरिथम लागत के अन्य उपायों पर लागू होता है

(ब्लम की स्पीड अप प्रमेय यह दर्शाता है कि "कम से कम" समय सामान्य रूप में प्राप्त नहीं किया जा सकता है ...)