CalcOpenly
हिन्दी

Big-O समय जटिलता कैलकुलेटर

अपने इनपुट आकार पर O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ) और O(n!) के संक्रिया-गणना और समय की तुलना लघुगणकीय आरेख में करें।

AI लेखन टूल से मसौदा तैयारअपडेट किया गया जाँचे गए उदाहरण: 6

= 1,000,000,000
आधुनिक CPU कोर के लिए लगभग 10⁹ सरल संक्रियाएँ प्रति सेकंड एक बहुत मोटा अनुमान है।
आज़माएँ
चलने का समय
9.966 µs
चलने का समय: 9.966 µs
चलने का समय, सेकंड में
0.000009966s
संक्रियाएँ
9,965.78
संक्रिया-गणना का log₁₀
3.9985
Big-O स्थिर गुणक और निचले क्रम के पद छोड़ देता है, इसलिए वास्तविक समय का स्थिर गुणक अलग हो सकता है।

n = 1,000 पर O(n log n) वृद्धि मॉडल लगभग 9,966 संक्रियाएँ देता है। 1,000,000,000 संक्रिया प्रति सेकंड पर इसमें 9.966 µs लगते हैं। आरेख की ऊपरी सीमा पर वक्र कटते हैं; केवल इससे जटिलता वर्ग तय नहीं होता।

लघुगणकीय पैमाने पर वृद्धि (शून्य गणनाएँ छोड़ी गई हैं)

02.557.5102004006008001,000nसंक्रियाओं का log₁₀एक सेकंड का काम
O(1)O(log n)O(n)O(n log n)O(n²)O(n³)O(2ⁿ)O(n!)
n = 1,000 पर हर वर्ग पंक्तियाँ: 8
वर्गसंक्रियाएँlog₁₀समय
O(1)101 ns
O(log n)9.96580.9999.966 ns
O(n)1,00031 µs
O(n log n)9,965.783.9999.966 µs
O(n²)1,000,00061 ms
O(n³)1,000,000,00091 s
O(2ⁿ)1.07151 × 10³⁰¹301.033.395 × 10²⁸⁴ वर्ष
O(n!)4.02387 × 10²⁵⁶⁷2,567.6051.275 × 10²⁵⁵¹ वर्ष
गणना कैसे होती है S

  1. संक्रियाएँ गिनें

    f(n)=nlog⁡2n=9,965.784(n=1000)f(n) = n \log_2 n = 9{,}965.784\quad (n = 1000)

    लघुगणक का आधार 2 है (आधा करना या द्विभाजन); दूसरा आधार केवल स्थिर गुणक बदलता है।

  2. मशीन की गति से भाग दें

    t=9,965.7841,000,000,000 s−1=0.000009966 st = \frac{9{,}965.784}{1{,}000{,}000{,}000\ \text{s}^{-1}} = 0.000009966\ \text{s}

  3. प्रचलित समय इकाइयों में लिखें

    9.966 µs

Big-O समय जटिलता कैलकुलेटर के बारे में

Big-O संकेत बताता है कि इनपुट आकार n बढ़ने पर एल्गोरिदम का काम कैसे बढ़ता है; इसमें स्थिर गुणक छोड़ दिए जाते हैं। यह कैलकुलेटर आपके n पर वृद्धि फलन f(n)—1, log2 n, n, n log2 n, n², n³, 2ⁿ और n!—निकालता है। फिर मशीन की प्रति सेकंड सरल संक्रियाओं की संख्या से भाग देकर समय का अनुमान देता है।

कोड लिखने से पहले किसी विधि की संभावित गति समझने में यह मदद करता है। डिफ़ॉल्ट n = 1,000 और 10^9 संक्रिया प्रति सेकंड पर n log n मॉडल लगभग 9,966 संक्रियाएँ और 10 µs देता है; n² में 1 ms लगता है। वहीं 2ⁿ मॉडल को केवल n = 100 पर लगभग 4.0 × 10^13 वर्ष चाहिए।

सूत्र में r प्रति सेकंड संक्रियाओं की संख्या है। समय को मोटे परिमाण का अनुमान मानें: वास्तविक कोड में स्थिर गुणक, कैश प्रभाव और निचले क्रम के पद होते हैं, जिन्हें Big-O छोड़ता है।

इनपुट आकार से काम और समय का अनुमान निकालें

चुना हुआ वृद्धि-फ़ंक्शन f(n) निकालें, फिर प्रति सेकंड ऑपरेशन r से भाग दें: समय = f(n) ÷ r। n = 1,000 पर n log₂ n ≈ 9,965.78 ऑपरेशन हैं। यदि r = 10⁹ हो तो लगभग 9.966 µs; उसी दर पर n² = 1,000,000 ऑपरेशन को 1 ms लगता है।

यह फ़ंक्शन और दर मानकर निकला मॉडल है। Big-O अपने आप वास्तविक सेकंड, मशीन की गति या छिपा स्थिरांक नहीं बताता। NIST की परिभाषा में किसी स्थिर c के लिए पर्याप्त बड़े n पर f(n) ≤ c·g(n) होता है।

वृद्धि की श्रेणी कैसे चुनें

एक ही काम, हर तत्व पर एक बार काम, और हर जोड़ी पर काम क्रमशः 1, n और n² जैसे मॉडल देते हैं। हर चरण में खोज-क्षेत्र आधा हो तो log₂ n उपयोगी तुलना है। फ़ंक्शन और n को उसी समस्या से जोड़ें जिसे आप मापना चाहते हैं।

n दोगुना करने पर n² का काम चार गुना और n³ का आठ गुना होता है। 2ⁿ में सिर्फ़ मशीन दस गुना तेज़ करने से हल होने वाला n लगभग 3.32 ही बढ़ता है। इसलिए बहुत बड़े इनपुट पर एल्गोरिद्म बदलना केवल हार्डवेयर तेज़ करने से अधिक असर डाल सकता है।

पाँच गणना उदाहरण

स्थितिमॉडल के ऑपरेशनमॉडल का समय
मूल उदाहरण9965.789.966 µs
एक हज़ार का वर्ग1.00000E+61 ms
सौ पर घातीय वृद्धि1.26765E+304.017 × 10¹³ वर्ष
बीस का फ़ैक्टोरियल2.43290E+1877.1 वर्ष
एक का लघुगणक00 s

पहली दो पंक्तियाँ n = 1,000 पर n log₂ n और n² हैं। तीसरी 2¹⁰⁰, चौथी 20!, और अंतिम log₂ 1 = 0 है। हर पंक्ति में दर 10⁹ ऑपरेशन/सेकंड है। E+30 का अर्थ ×10³⁰ है; यह मापी हुई बेंचमार्क रिपोर्ट नहीं है।

अपनी ऑपरेशन-दर मापें

यदि एक लाख समान ऑपरेशन में 0.2 सेकंड लगे तो दर 500,000 प्रति सेकंड है। किसी एक नेटवर्क अनुरोध या डिस्क पढ़ाई को CPU जोड़ जितना छोटा ऑपरेशन न मानें। इनपुट, कैश, मेमोरी आवंटन और I/O के साथ वास्तविक समय बदल सकता है।

औसत और सबसे खराब स्थिति भी अलग रखें। दो सूचियों के आकार n और m हों तो दोनों पर नेस्टेड लूप n·m है; सब कुछ एक n में छिपाने पर मॉडल गलत बनेगा। छोटे इनपुट पर स्थिरांक प्रभावी होते हैं, इसलिए अंतिम निर्णय अपने प्रोग्राम की प्रोफ़ाइल से करें।

डेटा भेजना मुख्य लागत हो तो बैंडविड्थ कैलकुलेटर में फ़ाइल आकार और वास्तविक थ्रूपुट से समय निकालें।

हल किए गए उदाहरण

n = 1,000 पर n²

इनपुट आकार n
1000
प्रति सेकंड संक्रियाएँ
1e9
आपका एल्गोरिदम
O(n²)
संक्रियाएँ
1,000,000
चलने का समय, सेकंड में
0.001 s
चलने का समय
1 ms

जाँच का स्रोत: स्वतंत्र गणना

n = 1,000 पर n log n

इनपुट आकार n
1000
प्रति सेकंड संक्रियाएँ
1e9
आपका एल्गोरिदम
O(n log n)
संक्रियाएँ
9,965.78
चलने का समय, सेकंड में
0.000009966 s

जाँच का स्रोत: स्वतंत्र गणना

n = 100 पर 2ⁿ

इनपुट आकार n
100
प्रति सेकंड संक्रियाएँ
1e9
आपका एल्गोरिदम
O(2ⁿ)
संक्रियाएँ
1.26765 × 10³⁰
संक्रिया-गणना का log₁₀
30.1030
चलने का समय
4.017 × 10¹³ years

जाँच का स्रोत: स्वतंत्र गणना

20! संक्रियाएँ

इनपुट आकार n
20
प्रति सेकंड संक्रियाएँ
1e9
आपका एल्गोरिदम
O(n!)
संक्रियाएँ
2.4329 × 10¹⁸
चलने का समय, सेकंड में
2,433,000,000 s

जाँच का स्रोत: स्वतंत्र गणना

सवाल

O(n log n) और O(n²) में क्या अंतर है?

n = 1,000 पर n log2 n लगभग 9,966 और n² = 1,000,000 है, यानी लगभग 100 गुना अंतर। n = 10 लाख पर अंतर लगभग 50,000 गुना है (2 × 10^7 बनाम 10^12)। इसलिए बड़े और प्रतिकूल इनपुट पर O(n log n) वाले मर्ज सॉर्ट और हीपसॉर्ट, O(n²) वाले इन्सर्शन सॉर्ट और बबल सॉर्ट से बेहतर बढ़ते हैं। छोटे या विशेष रूप से व्यवस्थित इनपुट में वास्तविक तुलना बदल सकती है।

O(log n) का क्या अर्थ है?

O(log n) में काम, इनपुट के लघुगणक के अनुसार बढ़ता है; अक्सर हर चरण में बचा हिस्सा आधा होता है, जैसे बाइनरी सर्च। n दोगुना करने पर लगभग एक चरण बढ़ता है: 1,000 क्रमबद्ध तत्वों में करीब 10 तुलनाएँ (log2 1,000 ≈ 9.97), और 10 लाख में करीब 20। लघुगणक का आधार केवल स्थिर गुणक बदलता है, इसलिए Big-O उसे छोड़ देता है।

O(2ⁿ) और O(n!) वाले एल्गोरिदम अव्यावहारिक क्यों हो सकते हैं?

हर अतिरिक्त तत्व के साथ उनका काम गुणात्मक रूप से बढ़ता है। n में 1 जोड़ने पर 2ⁿ दोगुना होता है। n = 100 पर लगभग 1.27 × 10^30 संक्रियाएँ होती हैं, या 10^9 प्रति सेकंड पर 4.0 × 10^13 वर्ष—ब्रह्मांड की आयु का लगभग 2,900 गुना। n! और तेज़ बढ़ता है: 20! ≈ 2.43 × 10^18, यानी लगभग 77 वर्ष। सभी उपसमुच्चयों या क्रमों की संपूर्ण खोज ऐसे वृद्धि मॉडल दे सकती है।

क्या Big-O वास्तविक चलने का समय बताता है?

नहीं। Big-O, n बढ़ने पर काम की सीमा बताता है और स्थिर गुणक तथा निचले क्रम के पद छोड़ देता है। इसलिए 3n² + 100n और n²/2 दोनों O(n²) हैं। दो O(n) एल्गोरिदम की गति कई गुना अलग हो सकती है; छोटे n पर O(n²) विधि, O(n log n) से तेज़ भी हो सकती है। यहाँ समय को मोटा अनुमान मानें और वास्तविक कोड को प्रोफ़ाइल करके मापें।

Big-O, Big-Omega और Big-Theta में क्या अंतर है?

Big-O आसन्न ऊपरी सीमा, Big-Omega (Ω) निचली सीमा और Big-Theta (Θ) दोनों को साथ बताने वाली सटीक वृद्धि सीमा है। मानक मर्ज सॉर्ट Θ(n log n) काम करता है। इन्सर्शन सॉर्ट प्रतिकूल स्थिति में O(n²) है, लेकिन पहले से क्रमबद्ध इनपुट पर केवल n − 1 तुलनाएँ करता है। Knuth ने 1976 में SIGACT News में ये परिभाषाएँ दीं; CLRS का अध्याय 3 इन्हीं का अनुसरण करता है।

इस कैलकुलेटर के बारे में

t=f(n)rf∈{1,log⁡2n,n,nlog⁡2n,n2,n3,2n,n!}\begin{aligned} t &= \frac{f(n)}{r} \\ f &\in \{1, \log_2 n, n, n\log_2 n, \\ &\qquad n^2, n^3, 2^n, n!\}\end{aligned}

स्रोत

  1. Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4th ed., ch. 3 (asymptotic notation)
  2. Knuth, “Big Omicron and big Omega and big Theta”, SIGACT News 8(2), 1976

संदर्भों से जाँच की गई

इस कैलकुलेटर में स्वतंत्र स्रोतों के उत्तरों वाले 6 हल किए गए उदाहरण शामिल हैं। ये परीक्षण समूह में चलते हैं और आप इन्हें यहाँ भी चला सकते हैं।

यह कैलकुलेटर अपनी वेबसाइट पर लगाएँ

जहाँ कैलकुलेटर दिखाना है, वहाँ इसे पेस्ट करें। इसका उपयोग मुफ़्त है, यहाँ किए गए सुधार इसमें अपने आप पहुँच जाते हैं, और उसके नीचे की श्रेय पंक्ति मूल पेज का लिंक देती है, जिससे आपके पाठक पूरा संस्करण देख सकते हैं।

ऊँचाई
एम्बेड का पूर्वावलोकन देखें

श्रेय पंक्ति बनी रहने दें। यही एकमात्र शर्त है, और इसी से ये कैलकुलेटर मुफ़्त रहते हैं।

संबंधित कैलकुलेटर