रैखिक समय बनाम। Quadratic समय

Question

अक्सर, कुछ उत्तरों का उल्लेख है कि दिया गया समाधान रैखिक है, या दूसरा एक वर्गवार है।

अंतर कैसे बनाएं/पहचानें कि क्या है?

क्या कोई मुझे इस तरह के लोगों के लिए सबसे आसान तरीका बता सकता है, जो अभी भी नहीं जानते हैं?

Answer 1

एक विधि रैखिक है जब इसमें शामिल तत्वों की संख्या के साथ रैखिक रूप से बढ़ता है।उदाहरण के लिए, पाश जो एक सरणी के तत्वों के प्रिंट के लिए एक मोटे तौर पर रैखिक है:

for x in range(10): 
    print x 

क्योंकि यदि हम सीमा (10) के बजाय सीमा (100) प्रिंट, समय यह इसे चलाने के लिए ले जाएगा 10 गुना है लंबे समय तक। आप बहुत बार है कि के रूप में हे (एन) लिखा देखेंगे, जिसका अर्थ है कि समय या एल्गोरिथ्म चलाने के लिए कम्प्यूटेशनल प्रयास

अब एन के लिए आनुपातिक है, मान लें कि हम छोरों के लिए दो के तत्वों को प्रिंट करना चाहते हैं:

for x in range(10): 
    for y in range(10): 
     print x, y 

प्रत्येक एक्स के लिए, मैं 10 बार लूपिंग वाई जाता हूं। इस कारण से, पूरी चीज 10x10 = 100 प्रिंटों के माध्यम से जाती है (आप उन्हें कोड चलाकर देख सकते हैं)। यदि 10 का उपयोग करने के बजाय, मैं 100 का उपयोग करता हूं, अब विधि 100x100 = 10000 करेगी। दूसरे शब्दों में, विधि ओ (एन * एन) या ओ (एन²) के रूप में जाती है, क्योंकि हर बार जब आप तत्वों की संख्या में वृद्धि करते हैं, तो गणना के प्रयास या समय अंक की संख्या के वर्ग के रूप में बढ़ेगा।

Answer 2

उन्हें रन-टाइम जटिलता का जिक्र करना चाहिए जिसे बिग ओ नोटेशन भी कहा जाता है। यह निपटने के लिए एक बहुत बड़ा विषय है। मैं विकिपीडिया पर लेख के साथ शुरू करूंगा: https://en.wikipedia.org/wiki/Big_O_notation

जब मैं इस विषय पर शोध कर रहा था, तो मैंने जो कुछ करना सीखा वह डेटा के विभिन्न आकार सेट के साथ मेरे एल्गोरिदम का रनटाइम ग्राफ है। जब आप परिणाम ग्राफ करते हैं तो आप देखेंगे कि रेखा या वक्र को विकास के कई आदेशों में से एक में वर्गीकृत किया जा सकता है।

एल्गोरिदम की रनटाइम जटिलता को वर्गीकृत करने के तरीके को समझना आपको यह समझने के लिए एक ढांचा देगा कि आपका एल्गोरिदम समय या स्मृति के मामले में कैसे स्केल करेगा। यह आपको एक-दूसरे के साथ कम से कम एल्गोरिदम की तुलना करने और वर्गीकृत करने की शक्ति देगा।

मैं कोई विशेषज्ञ नहीं हूं लेकिन इससे मुझे खरगोश छेद शुरू करने में मदद मिली।

यहाँ विकास की कुछ विशिष्ट आदेश हैं: - लगातार समय

हे (लॉग एन) - लघुगणक

हे (एन) -

• हे (1) रैखिक समय
• ओ (n^2) - द्विघात
• हे (2^n) - घातीय
• हे (एन) - भाज्य

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

शुभकामनाएं!

Answer 3

आप आमतौर पर उनके इनपुट आकार n (यदि इनपुट एक सरणी या सूची है) के संदर्भ में एल्गोरिदम के बारे में बहस करते हैं। किसी समस्या का एक रैखिक समाधान एक एल्गोरिदम होगा जो निष्पादन समय n के साथ रैखिक स्केल करता है, इसलिए x*n + y, जहां x और y वास्तविक संख्याएं हैं। n 1: n = n^1 के उच्चतम एक्सपोनेंट के साथ प्रकट होता है।

एक वर्गबद्ध समाधान के साथ, n 2 शब्द के साथ उच्चतम एक्सपोनेंट के रूप में दिखाई देता है, उदाहरण के लिए x*n^2 + y*n + z।

मनमाने ढंग से n के लिए, रैखिक समाधान निष्पादन समय में चौकोर वर्ग से बहुत धीमा हो जाता है।

mor जानकारी के लिए, Big O Notation देखें।

Answer 4

आप निर्दिष्ट नहीं करते हैं लेकिन जैसा कि आप समाधान का उल्लेख करते हैं, यह संभव है कि आप वर्गबद्ध और रैखिक अभिसरण के बारे में पूछ रहे हों। इस उद्देश्य से, अगर आप एक एल्गोरिथ्म है कि पुनरावृत्ति है और एक संसृत मूल्य के अनुमानों के अनुक्रम उत्पन्न करता है, तो आप द्विघात अभिसरण है जब आप दिखा सकते हैं कि

x(n) <= c * x(n-1)^2 

कुछ सकारात्मक निरंतर c के लिए

। यही कहना है कि पुनरावृत्ति n+1 पर समाधान में त्रुटि n पर त्रुटि के वर्ग से कम है। अधिक सामान्य अभिसरण दर परिभाषाओं के लिए एक पूर्ण परिचय के लिए इसे देखें http://en.wikipedia.org/wiki/Rate_of_convergence