Big O दौड

वस्तुको सङ्ख्या 8 देखि 1024 सम्म बढ्दा hash lookup, binary search, linear search, merge sort र bubble sort लाई दौडाउनुहोस्। केही रेखा मुस्किलले माथि जान्छन् तर bubble sort पाँच लाख चरणभन्दा माथि पुग्छ, हेर्नुहोस्, र हरेकको बढाइका Big O नाम सिक्नुहोस्।

मूल अवधारणा

Big O ले input को आकार n अनुसार algorithm का चरण कसरी बढ्छन् भन्छ: n दोब्बर हुँदा O(1) उस्तै रहन्छ, O(log n) एकले बढ्छ, O(n) दोब्बर हुन्छ, O(n log n) दोब्बरभन्दा अलि बढी, र O(n²) चार गुणा

पाठ: Algorithm को दक्षता

दुई प्रोग्रामले उही उत्तर दिए पनि तिनलाई धेरै फरक काम लाग्न सक्छ। प्रोग्रामरहरू यसलाई Big O ले बताउँछन्: input, n वटा वस्तु, ठूलो हुँदै जाँदा चरण कसरी बढ्छन्। Hash table lookup ले table जति ठूलो भए पनि करिब उही एउटा चरण लिन्छ: O(1)। Binary: 0 र 1 दुई अङ्क मात्र प्रयोग गरेर गन्ने तरिका। कम्प्युटरले सबै कुरा यसरी राख्छ। सबै मुख्य शब्द search ले हरेक पटक सूची आधा गर्छ, त्यसैले n दोब्बर हुँदा एउटा मात्र चरण थपिन्छ: O(log n)। Linear search ले हरेक वस्तु हेर्न सक्छ: O(n), त्यसैले n दोब्बर हुँदा काम दोब्बर हुन्छ। Merge sort O(n log n) हो, दोब्बरभन्दा अलि बढी। Bubble sort ले हरेक जोडी दाँज्छ: O(n²), त्यसैले n दोब्बर हुँदा चार गुणा काम हुन्छ। 8 वटा वस्तुमा फरक सानो हुन्छ; 1024 वटामा विशाल।

मुख्य शब्दको अर्थ