पुनरावृत्त लघुगणक: Difference between revisions
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
[[सकारात्मक वास्तविक संख्या]]ओं पर, निरंतर सुपर-लघुगणक (व्युत्क्रम चतुष्कोण) अनिवार्य रूप से समतुल्य है: | [[सकारात्मक वास्तविक संख्या|धनात्मक वास्तविक संख्या]]ओं पर, निरंतर सुपर-लघुगणक (व्युत्क्रम चतुष्कोण) अनिवार्य रूप से समतुल्य है: | ||
:<math>\log^* n = \lceil \mathrm {slog}_e(n) \rceil</math> | :<math>\log^* n = \lceil \mathrm {slog}_e(n) \rceil</math> | ||
अथार्त आधार b पुनरावृत्त लघुगणक <math>\log^* n = y</math> है यदि n अंतराल <math>^{y-1}b<n\leq\ ^{y}b</math> के अंदर स्थित है, जहां <math>{^{y}b} = \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_y</math><nowiki> _{y}} टेट्रेशन को दर्शाता है। चूँकि | अथार्त आधार b पुनरावृत्त लघुगणक <math>\log^* n = y</math> है यदि n अंतराल <math>^{y-1}b<n\leq\ ^{y}b</math> के अंदर स्थित है, जहां <math>{^{y}b} = \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_y</math><nowiki> _{y}} टेट्रेशन को दर्शाता है। चूँकि ऋणात्मक वास्तविक संख्याओं पर, लॉग-स्टार </nowiki><math>0</math> है, जबकि धनात्मक x के लिए <math>\lceil \text{slog}_e(-x)\rceil = -1</math> है, इसलिए ऋणात्मक तर्कों के लिए दोनों फलन भिन्न हैं।[[Image:Iterated logarithm.png|right|300px|thumb|चित्र 1. बेस-ई पुनरावृत्त लघुगणक के लिए log* 4 = 2 प्रदर्शित करना है पुनरावृत्त लघुगणक का मान इनपुट n से अंतराल [0,1] तक वक्र y = log<sub>b</sub>(x) पर "ज़िग-ज़ैगिंग" द्वारा पाया जा सकता है। इस स्थिति में, b = e. ज़िग-ज़ैगिंग में बिंदु (n, 0) से प्रारंभ करना और पुनरावृत्त रूप से (n, log<sub>b</sub>(n) ),से (0, log<sub>b</sub>(n) ), to (log<sub>b</sub>(n), 0 ) तक जाना सम्मिलित है।]]पुनरावृत्त लघुगणक किसी भी धनात्मक वास्तविक संख्या को स्वीकार करता है और एक पूर्णांक उत्पन्न करता है। ग्राफ़िक रूप से, इसे चित्र 1 में x-अक्ष पर अंतराल <math>[0, 1]</math> तक पहुंचने के लिए आवश्यक "ज़िग-ज़ैग" की संख्या के रूप में समझा जा सकता है। | ||
कंप्यूटर विज्ञान में, {{lg-star}} का उपयोग अधिकांशतः बाइनरी पुनरावृत्त लघुगणक को इंगित करने के लिए किया जाता है, जो प्राकृतिक लघुगणक (आधार ई के साथ) के अतिरिक्त बाइनरी लघुगणक (आधार <math>2</math> के साथ) को पुनरावृत्त करता है। | कंप्यूटर विज्ञान में, {{lg-star}} का उपयोग अधिकांशतः बाइनरी पुनरावृत्त लघुगणक को इंगित करने के लिए किया जाता है, जो प्राकृतिक लघुगणक (आधार ई के साथ) के अतिरिक्त बाइनरी लघुगणक (आधार <math>2</math> के साथ) को पुनरावृत्त करता है। | ||
गणितीय रूप से, पुनरावृत्त लघुगणक केवल आधार <math>2</math> और आधार ''e'' के लिए ही नहीं, किन्तु <math>e^{1/e} \approx 1.444667</math> लगभग 1.444667} से बड़े किसी भी आधार के लिए अच्छी तरह से परिभाषित है। | गणितीय रूप से, पुनरावृत्त लघुगणक केवल आधार <math>2</math> और आधार ''e'' के लिए ही नहीं, किन्तु <math>e^{1/e} \approx 1.444667</math> लगभग 1.444667} से बड़े किसी भी आधार के लिए अच्छी तरह से परिभाषित है। | ||
| Line 59: | Line 57: | ||
| year = 1986| doi-access = free | | year = 1986| doi-access = free | ||
}}</ref> | }}</ref> | ||
पुनरावृत्त लघुगणक अत्यंत धीमी गति से बढ़ता है, लघुगणक की तुलना में बहुत धीमी गति | पुनरावृत्त लघुगणक अत्यंत धीमी गति से बढ़ता है, लघुगणक की तुलना में बहुत धीमी गति से n के सभी मानो के लिए अभ्यास में कार्यान्वित एल्गोरिदम के चलने के समय की गणना करने के लिए प्रासंगिक (अथार्त, n ≤ 2<sup>65536</sup>, जो ज्ञात ब्रह्मांड में परमाणुओं की अनुमानित संख्या से कहीं अधिक है), आधार 2 के साथ पुनरावृत्त लघुगणक का मान 5 से अधिक नहीं है। | ||
{|class=wikitable | {|class=wikitable | ||
| Line 77: | Line 75: | ||
| {{open-closed|65536, 2<sup>65536</sup>}} || 5 | | {{open-closed|65536, 2<sup>65536</sup>}} || 5 | ||
|} | |} | ||
उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। वास्तव में, जटिलता सिद्धांत में सामान्यतः उपयोग किया जाने वाला एकमात्र फलन जो अधिक धीरे-धीरे बढ़ता है वह उलटा एकरमैन फलन है। | उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। वास्तव में, जटिलता सिद्धांत में सामान्यतः उपयोग किया जाने वाला एकमात्र फलन जो अधिक धीरे-धीरे बढ़ता है वह उलटा एकरमैन फलन है। | ||
Revision as of 21:37, 12 July 2023
कंप्यूटर विज्ञान में, का पुनरावृत्त लघुगणक लिखित हुआ log* (सामान्यतः लॉग स्टार पढ़ा जाता है), परिणाम से कम या उसके समान होने से पहले लघुगणक कार्य को पुनरावृति प्रयुक्त करने की संख्या है[1] सबसे सरल औपचारिक परिभाषा इस पुनरावृत्ति संबंध का परिणाम है:
धनात्मक वास्तविक संख्याओं पर, निरंतर सुपर-लघुगणक (व्युत्क्रम चतुष्कोण) अनिवार्य रूप से समतुल्य है:
अथार्त आधार b पुनरावृत्त लघुगणक है यदि n अंतराल के अंदर स्थित है, जहां _{y}} टेट्रेशन को दर्शाता है। चूँकि ऋणात्मक वास्तविक संख्याओं पर, लॉग-स्टार है, जबकि धनात्मक x के लिए है, इसलिए ऋणात्मक तर्कों के लिए दोनों फलन भिन्न हैं।
पुनरावृत्त लघुगणक किसी भी धनात्मक वास्तविक संख्या को स्वीकार करता है और एक पूर्णांक उत्पन्न करता है। ग्राफ़िक रूप से, इसे चित्र 1 में x-अक्ष पर अंतराल तक पहुंचने के लिए आवश्यक "ज़िग-ज़ैग" की संख्या के रूप में समझा जा सकता है।
कंप्यूटर विज्ञान में, lg* का उपयोग अधिकांशतः बाइनरी पुनरावृत्त लघुगणक को इंगित करने के लिए किया जाता है, जो प्राकृतिक लघुगणक (आधार ई के साथ) के अतिरिक्त बाइनरी लघुगणक (आधार के साथ) को पुनरावृत्त करता है।
गणितीय रूप से, पुनरावृत्त लघुगणक केवल आधार और आधार e के लिए ही नहीं, किन्तु लगभग 1.444667} से बड़े किसी भी आधार के लिए अच्छी तरह से परिभाषित है।
एल्गोरिदम का विश्लेषण
पुनरावृत्त लघुगणक एल्गोरिदम और कम्प्यूटेशनल जटिलता सिद्धांत के विश्लेषण में उपयोगी है, जो कुछ एल्गोरिदम के समय और स्थान जटिलता सीमा में दिखाई देता है:
- यूक्लिडियन न्यूनतम फैले हुए पेड़ को यादृच्छिक O(n log* n) समय को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाया जाता है।[2]
- पूर्णांक गुणन के लिए फ्यूरर का एल्गोरिदम: O(n log n 2O(lg* n)).
- अनुमानित अधिकतम खोज (तत्व कम से कम माध्यिका जितना बड़ा):lg* n − 4 to lg* n + 2 समानांतर संचालन।[3]
- एन-चक्र को 3-रंग देने के लिए रिचर्ड कोल और उजी विश्किन का वितरित एल्गोरिदम: O(log* n) सिंक्रोनस संचार राउंड।[4]
पुनरावृत्त लघुगणक अत्यंत धीमी गति से बढ़ता है, लघुगणक की तुलना में बहुत धीमी गति से n के सभी मानो के लिए अभ्यास में कार्यान्वित एल्गोरिदम के चलने के समय की गणना करने के लिए प्रासंगिक (अथार्त, n ≤ 265536, जो ज्ञात ब्रह्मांड में परमाणुओं की अनुमानित संख्या से कहीं अधिक है), आधार 2 के साथ पुनरावृत्त लघुगणक का मान 5 से अधिक नहीं है।
| x | lg* x |
|---|---|
| (−∞, 1] | 0 |
| (1, 2] | 1 |
| (2, 4] | 2 |
| (4, 16] | 3 |
| (16, 65536] | 4 |
| (65536, 265536] | 5 |
उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। वास्तव में, जटिलता सिद्धांत में सामान्यतः उपयोग किया जाने वाला एकमात्र फलन जो अधिक धीरे-धीरे बढ़ता है वह उलटा एकरमैन फलन है।
अन्य अनुप्रयोग
पुनरावृत्त लघुगणक सममित स्तर-सूचकांक अंकगणित में उपयोग किए जाने वाले सामान्यीकृत लघुगणक फलन से निकटता से संबंधित है। किसी संख्या की योगात्मक दृढ़ता, किसी को उसके डिजिटल रूट तक पहुंचने से पहले संख्या को उसके अंकों के योग से बदलने की संख्या है।
कम्प्यूटेशनल जटिलता सिद्धांत में, संथानम [5] दर्शाता है कि कम्प्यूटेशनल संसाधन डीटाइम - एक नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - और एनटाइम- एक गैर-नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - तक भिन्न हैं।
संदर्भ
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "The iterated logarithm function, in Section 3.2: Standard notations and common functions". Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 58–59. ISBN 0-262-03384-4.
- ↑ Devillers, Olivier (1992). "Randomization yields simple algorithms for difficult problems". International Journal of Computational Geometry & Applications. 2 (1): 97–111. doi:10.1142/S021819599200007X. MR 1159844. S2CID 60203.
- ↑ Alon, Noga; Azar, Yossi (1989). "Finding an approximate maximum". SIAM Journal on Computing. 18 (2): 258–267. doi:10.1137/0218017. MR 0986665.
- ↑ Cole, Richard; Vishkin, Uzi (1986). "Deterministic coin tossing with applications to optimal parallel list ranking". Information and Control. 70 (1): 32–53. doi:10.1016/S0019-9958(86)80023-7. MR 0853994.
- ↑ Santhanam, Rahul (2001). "On separators, segregators and time versus space" (PDF). Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001. IEEE Computer Society. pp. 286–294. doi:10.1109/CCC.2001.933895.
