पुनरावृत्त लघुगणक: Difference between revisions

Revision as of 20:24, 10 July 2023

कंप्यूटर विज्ञान में, $n$ का पुनरावृत्त लघुगणक लिखित हुआ log* $n$ (सामान्यतः लॉग स्टार पढ़ा जाता है), परिणाम $1$ से कम या उसके समान होने से पहले लघुगणक कार्य को पुनरावृति प्रयुक्त करने की संख्या है^[1] सबसे सरल औपचारिक परिभाषा इस पुनरावृत्ति संबंध का परिणाम है:

\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}

सकारात्मक वास्तविक संख्याओं पर, निरंतर सुपर-लघुगणक (व्युत्क्रम चतुष्कोण) अनिवार्य रूप से समतुल्य है:

\log ^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil

अथार्त आधार b पुनरावृत्त लघुगणक $\log ^{*}n=y$ है यदि n अंतराल $^{y-1}b<n\leq \ ^{y}b$ के अंदर स्थित है, जहां ${^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}$ _{y}} टेट्रेशन को दर्शाता है। चूँकि नकारात्मक वास्तविक संख्याओं पर, लॉग-स्टार $0$ है, जबकि सकारात्मक x के लिए $\lceil {\text{slog}}_{e}(-x)\rceil =-1$ है, इसलिए नकारात्मक तर्कों के लिए दोनों फलन भिन्न हैं।

चित्र 1. बेस-ई पुनरावृत्त लघुगणक के लिए log* 4 = 2 प्रदर्शित करना है पुनरावृत्त लघुगणक का मान इनपुट n से अंतराल [0,1] तक वक्र y = log_b(x) पर "ज़िग-ज़ैगिंग" द्वारा पाया जा सकता है। इस स्थिति में, b = e. ज़िग-ज़ैगिंग में बिंदु (n, 0) से प्रारंभ करना और पुनरावृत्त रूप से (n, log_b(n) ),से (0, log_b(n) ), to (log_b(n), 0 ) तक जाना सम्मिलित है।

पुनरावृत्त लघुगणक किसी भी सकारात्मक वास्तविक संख्या को स्वीकार करता है और एक पूर्णांक उत्पन्न करता है। ग्राफ़िक रूप से, इसे चित्र 1 में x-अक्ष पर अंतराल $[0,1]$ तक पहुंचने के लिए आवश्यक "ज़िग-ज़ैग" की संख्या के रूप में समझा जा सकता है।

कंप्यूटर विज्ञान में, lg* का उपयोग अधिकांशतः बाइनरी पुनरावृत्त लघुगणक को इंगित करने के लिए किया जाता है, जो प्राकृतिक लघुगणक (आधार ई के साथ) के अतिरिक्त बाइनरी लघुगणक (आधार $2$ के साथ) को पुनरावृत्त करता है।

गणितीय रूप से, पुनरावृत्त लघुगणक से बड़े किसी भी आधार के लिए अच्छी तरह से परिभाषित है $e^{1/e}\approx 1.444667$ , न केवल आधार के लिए $2$ और बेस ई।

गणितीय रूप से, पुनरावृत्त लघुगणक केवल आधार $2$ और आधार e के लिए ही नहीं, किन्तु $e^{1/e}\approx 1.444667$ लगभग 1.444667} से बड़े किसी भी आधार के लिए अच्छी तरह से परिभाषित है।

एल्गोरिदम का विश्लेषण

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

यूक्लिडियन न्यूनतम फैले हुए पेड़ को यादृच्छिक O(n log* n) समय को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाया जाता है।^[2]
पूर्णांक गुणन के लिए फ्यूरर का एल्गोरिदम: O(n log n 2^{O(lg* n)}).
अनुमानित अधिकतम खोज (तत्व कम से कम माध्यिका जितना बड़ा):lg* n − 4 to lg* n + 2 समानांतर संचालन।^[3]
एन-चक्र को 3-रंग देने के लिए रिचर्ड कोल और उजी विश्किन का वितरित एल्गोरिदम: O(log* n) सिंक्रोनस संचार राउंड।^[4]

पुनरावृत्त लघुगणक अत्यंत धीमी गति से बढ़ता है, लघुगणक की तुलना में बहुत धीमी गति से। n के सभी मानो के लिए अभ्यास में कार्यान्वित एल्गोरिदम के चलने के समय की गणना करने के लिए प्रासंगिक (अथार्त, n ≤ 2⁶⁵⁵³⁶, जो ज्ञात ब्रह्मांड में परमाणुओं की अनुमानित संख्या से कहीं अधिक है), आधार 2 के साथ पुनरावृत्त लघुगणक का मान 5 से अधिक नहीं है।

आधार-2 पुनरावृत्त लघुगणक
x	lg* x
$(-\infty, 1]$	0
$(1, 2]$	1
$(2, 4]$	2
$(4, 16]$	3
$(16, 65536]$	4
$(65536, 2 65536]$	5

उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। वास्तव में, जटिलता सिद्धांत में सामान्यतः उपयोग किया जाने वाला एकमात्र फलन जो अधिक धीरे-धीरे बढ़ता है वह उलटा एकरमैन फलन है।

अन्य अनुप्रयोग

पुनरावृत्त लघुगणक सममित स्तर-सूचकांक अंकगणित में उपयोग किए जाने वाले सामान्यीकृत लघुगणक फलन से निकटता से संबंधित है। किसी संख्या की योगात्मक दृढ़ता, किसी को उसके डिजिटल रूट तक पहुंचने से पहले संख्या को उसके अंकों के योग से बदलने की संख्या $O(\log ^{*}n)$ है।

कम्प्यूटेशनल जटिलता सिद्धांत में, संथानम ^[5] दर्शाता है कि कम्प्यूटेशनल संसाधन डीटाइम - एक नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - और एनटाइम- एक गैर-नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - $n{\sqrt {\log ^{*}n}}.$ तक भिन्न हैं।

संदर्भ

↑ 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 $O(n\log ^{\ast }n)$ algorithms for difficult $\Omega (n)$ 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.

[1] 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.

[2] Devillers, Olivier (1992). "Randomization yields simple $O(n\log ^{\ast }n)$ algorithms for difficult $\Omega (n)$ problems". International Journal of Computational Geometry & Applications. 2 (1): 97–111. doi:10.1142/S021819599200007X. MR 1159844. S2CID 60203.

[3] Alon, Noga; Azar, Yossi (1989). "Finding an approximate maximum". SIAM Journal on Computing. 18 (2): 258–267. doi:10.1137/0218017. MR 0986665.

[4] 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.

[5] 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.

[1]

[2]

[3]

[4]

[5]

@@ Line 13: / Line 13: @@
 :<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}} टेट्रेशन को दर्शाता है। चूँकि नकारात्मक वास्तविक संख्याओं पर, लॉग-स्टार </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> तक पहुंचने के लिए आवश्यक "ज़िग-ज़ैग" की संख्या के रूप में समझा जा सकता है।
+अथार्त आधार 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>e^{1/e} \approx 1.444667</math>, न केवल आधार के लिए <math>2</math> और बेस ई।
@@ Line 24: / Line 24: @@
 पुनरावृत्त लघुगणक एल्गोरिदम और [[कम्प्यूटेशनल जटिलता सिद्धांत]] के विश्लेषण में उपयोगी है, जो कुछ एल्गोरिदम के समय और स्थान जटिलता सीमा में दिखाई देता है:
-*यूक्लिडियन न्यूनतम फैले हुए पेड़ को यादृच्छिक  O(''n'' log* ''n'') समय को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाया जाता है।<ref>{{cite journal
+*यूक्लिडियन न्यूनतम फैले हुए पेड़ को यादृच्छिक O(''n'' log* ''n'') समय को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाया जाता है।<ref>{{cite journal
   | last = Devillers | first = Olivier
   | doi = 10.1142/S021819599200007X
@@ Line 36: / Line 36: @@
   }}</ref>
 *पूर्णांक गुणन के लिए फ्यूरर का एल्गोरिदम: O(''n'' log ''n'' 2<sup>''O''(lg* ''n'')</sup>).
-* अनुमानित अधिकतम खोज (तत्व कम से कम माध्यिका जितना बड़ा):lg* ''n'' − 4 to lg* ''n'' + 2  समानांतर संचालन।<ref>{{cite journal
+* अनुमानित अधिकतम खोज (तत्व कम से कम माध्यिका जितना बड़ा):lg* ''n'' − 4 to lg* ''n'' + 2 समानांतर संचालन।<ref>{{cite journal
   | last1 = Alon | first1 = Noga | author1-link = Noga Alon
   | last2 = Azar | first2 = Yossi
@@ Line 80: / Line 80: @@
 उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। वास्तव में, जटिलता सिद्धांत में सामान्यतः उपयोग किया जाने वाला एकमात्र फलन जो अधिक धीरे-धीरे बढ़ता है वह उलटा एकरमैन फलन है।
-'''रावृत्त लघुगणक सममित स्तर-सूचकांक अंकगणित में उपयोग किएर-सूचकांक अंकगणित में उपयोग कि'''
 == अन्य अनुप्रयोग ==

Anonymous

Search

पुनरावृत्त लघुगणक: Difference between revisions

Namespaces

More

Page actions

Revision as of 20:24, 10 July 2023

एल्गोरिदम का विश्लेषण

अन्य अनुप्रयोग

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

पुनरावृत्त लघुगणक: Difference between revisions

Revision as of 20:24, 10 July 2023

एल्गोरिदम का विश्लेषण

अन्य अनुप्रयोग

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories