काम कति छिटो बढ्छ?
एउटै n का लागि तीनवटा साना प्रोग्रामले लिने चरण गन्नुहोस्: एउटा loop, loop भित्र अर्को loop, र n लाई आधा गर्दै जाने loop। n दोब्बर गर्नुहोस् र एउटा count दोब्बर, एउटा चार गुणा, र एउटा खासै नबढेको हेर्नुहोस्: Big O को पहिलो झलक।
मूल अवधारणा
प्रोग्रामले गर्ने काम input अनुसार बढ्छ: n वटा वस्तुमा एउटा loop ले करिब n चरण लिन्छ, loop भित्रको loop ले n × n, र हरेक पटक n आधा गर्दा करिब log₂ n मात्र; Big O ले यो बढोत्तरीलाई नाम दिन्छ
पाठ: Algorithm को दक्षता
दुईवटा प्रोग्रामले एउटै उत्तर दिए पनि फरक-फरक मात्राको काम गर्न सक्छन्। तिनलाई दाँज्न हामी input n बढ्दै जाँदा तिनका चरण गन्छौँ। एउटा Loop: दोहोरिने चरणहरू, निश्चित पटक वा कुनै कुरा सत्य नभएसम्म। सबै मुख्य शब्द FOR i FROM 1 TO n ले आफ्नो काम n पटक गर्छ। Loop भित्रको loop ले बाहिरी n वटा फन्को मध्ये हरेकमा भित्री काम n पटक गर्छ: n × n पटक। हरेक पटक n लाई आधा गर्ने loop, जस्तै WHILE m > 1 DO m ← m ÷ 2, लाई थोरै फन्को मात्र चाहिन्छ, करिब log₂ n। Programmer हरू यो बढोत्तरीलाई Big O notation मा लेख्छन्: एउटा loop का लागि O(n), loop भित्रको loop का लागि O(n²) र आधा गर्ने loop का लागि O(log n)। सानो n मा फरक थोरै हुन्छ, तर n दोब्बर हुँदा n² चार गुणा बढ्छ, त्यसैले loop भित्रको loop चाँडै ढिलो हुन्छ।
के सिक्नुहुनेछ
- दिइएको n का लागि एउटा loop र loop भित्रको loop का चरण गन्नुहोस्।
- n दोब्बर हुँदा हरेक count कसरी बदलिन्छ, अनुमान गर्नुहोस्।
- आधा गर्दा किन यति थोरै चरण लाग्छ, व्याख्या गर्नुहोस्।
- O(n), O(n²) र O(log n) को नाम लिनुहोस् र कुन सबैभन्दा छिटो बढ्छ भन्नुहोस्।
सुरु गर्नुअघि
- For loop, loop भित्रको loop र while loop कसरी दोहोरिन्छन्, थाहा हुनुपर्छ।
सामग्री
- n र तीनवटा count को तालिका बनाउन कापी
उपकरण
- केही पनि चाहिँदैन
विधि
- n = 4 राखेर प्रोग्राम चलाउनुहोस् र तीनवटै count पढ्नुहोस्।
- n लाई 8 मा दोब्बर गरेर count हरू दाँज्नुहोस्।
- n = 2 चलाएर हेर्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।