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

Revision as of 20:15, 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. आधार-ई पुनरावृत्त लघुगणक के लिए लॉग* 4 = 2 प्रदर्शित करना। पुनरावृत्त लघुगणक का मान वक्र y = log पर ज़िग-ज़ैगिंग द्वारा पाया जा सकता है_b(x) इनपुट n से, अंतराल [0,1] तक। इस मामले में, बी = ई। ज़िग-ज़ैगिंग बिंदु (n, 0) से शुरू होता है और पुनरावृत्त रूप से (n, log_b(एन)), से (0, लॉग_b(एन)), से (लॉग_b(एन), 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 1: / Line 1: @@
 {{Short description|Inverse function to a tower of powers}}
-{{For|the theorem in probability theory|Law of the iterated logarithm}}
+{{For|संभाव्यता सिद्धांत में प्रमेय|पुनरावृत्त लघुगणक का नियम}}
-[[कंप्यूटर विज्ञान]] में, का पुनरावृत्त लघुगणक <math>n</math>, लिखा हुआ {{log-star}} <math>n</math> (आमतौर पर लॉग स्टार पढ़ा जाता है), परिणाम से कम या उसके बराबर होने से पहले लघुगणक फ़ंक्शन को पुनरावृति लागू करने की संख्या है <math>1</math>.<ref>{{Introduction to Algorithms|3|chapter=The iterated logarithm function, in Section 3.2: Standard notations and common functions|pages=58–59}}</ref> सबसे सरल औपचारिक परिभाषा इस [[पुनरावृत्ति संबंध]] का परिणाम है:
+[[कंप्यूटर विज्ञान]] में, <math>n</math> का पुनरावृत्त लघुगणक लिखित हुआ {{log-star}} <math>n</math> (सामान्यतः लॉग स्टार पढ़ा जाता है), परिणाम <math>1</math> से कम या उसके समान होने से पहले लघुगणक कार्य को पुनरावृति प्रयुक्त करने की संख्या है<ref>{{Introduction to Algorithms|3|chapter=The iterated logarithm function, in Section 3.2: Standard notations and common functions|pages=58–59}}</ref> सबसे सरल औपचारिक परिभाषा इस [[पुनरावृत्ति संबंध]] का परिणाम है:
 :<math>
@@ Line 13: / Line 13: @@
 :<math>\log^* n = \lceil \mathrm {slog}_e(n) \rceil</math>
-यानी आधार बी पुनरावृत्त लघुगणक है <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>टेट्रेशन को दर्शाता है। हालाँकि, ऋणात्मक वास्तविक संख्याओं पर, लॉग-स्टार है <math>0</math>, जबकि <math>\lceil \text{slog}_e(-x)\rceil = -1</math> सकारात्मक के लिए <math>x</math>, so the two functions differ for negative arguments.[[Image:Iterated logarithm.png|right|300px|thumb|चित्र 1. आधार-ई पुनरावृत्त लघुगणक के लिए लॉग* 4 = 2 प्रदर्शित करना। पुनरावृत्त लघुगणक का मान वक्र y = log पर ज़िग-ज़ैगिंग द्वारा पाया जा सकता है<sub>b</sub>(x) इनपुट n से, अंतराल [0,1] तक। इस मामले में, बी = ई। ज़िग-ज़ैगिंग बिंदु (n, 0) से शुरू होता है और पुनरावृत्त रूप से (n, log<sub>b</sub>(एन)), से (0, लॉग<sub>b</sub>(एन)), से (लॉग<sub>b</sub>(एन), 0)।]]पुनरावृत्त लघुगणक किसी भी सकारात्मक [[वास्तविक संख्या]] को स्वीकार करता है और एक [[पूर्णांक]] उत्पन्न करता है। आलेखीय रूप से, इसे चित्र 1 में अंतराल तक पहुँचने के लिए आवश्यक ज़िग-ज़ैग की संख्या के रूप में समझा जा सकता है <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. आधार-ई पुनरावृत्त लघुगणक के लिए लॉग* 4 = 2 प्रदर्शित करना। पुनरावृत्त लघुगणक का मान वक्र y = log पर ज़िग-ज़ैगिंग द्वारा पाया जा सकता है<sub>b</sub>(x) इनपुट n से, अंतराल [0,1] तक। इस मामले में, बी = ई। ज़िग-ज़ैगिंग बिंदु (n, 0) से शुरू होता है और पुनरावृत्त रूप से (n, log<sub>b</sub>(एन)), से (0, लॉग<sub>b</sub>(एन)), से (लॉग<sub>b</sub>(एन), 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> और बेस ई।
+गणितीय रूप से, पुनरावृत्त लघुगणक केवल आधार <math>2</math> और आधार ''e'' के लिए ही नहीं, किन्तु <math>e^{1/e} \approx 1.444667</math> लगभग 1.444667} से बड़े किसी भी आधार के लिए अच्छी तरह से परिभाषित है।
 == [[एल्गोरिदम का विश्लेषण]] ==
 पुनरावृत्त लघुगणक एल्गोरिदम और [[कम्प्यूटेशनल जटिलता सिद्धांत]] के विश्लेषण में उपयोगी है, जो कुछ एल्गोरिदम के समय और स्थान जटिलता सीमा में दिखाई देता है:
-* यूक्लिडियन न्यूनतम फैले हुए पेड़ को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाना: यादृच्छिक [[बिग-ओ नोटेशन]] (एन{{log-star}}एन) समय।<ref>{{cite journal
+*यूक्लिडियन न्यूनतम फैले हुए पेड़ को यादृच्छिक  O(''n'' log* ''n'') समय को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाया जाता है।<ref>{{cite journal
   | last = Devillers | first = Olivier
   | doi = 10.1142/S021819599200007X
@@ Line 33: / Line 35: @@
   | year = 1992| s2cid = 60203
   }}</ref>
-* पूर्णांक गुणन के लिए फ्यूरर का एल्गोरिदम: O(n log n 2<sup>हे({{lg-star}}एन)</सुप>).
+*पूर्णांक गुणन के लिए फ्यूरर का एल्गोरिदम: O(''n'' log ''n'' 2<sup>''O''(lg* ''n'')</sup>).
-* अनुमानित अधिकतम ढूँढना (तत्व कम से कम माध्यिका जितना बड़ा): {{lg-star}}एन - 4 से {{lg-star}}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 45: / Line 47: @@
   | volume = 18
   | year = 1989}}</ref>
-* रिचर्ड कोल और [[उजी विस्किन]] का ग्राफ कलरिंग # समानांतर और वितरित एल्गोरिदम | एन-साइकिल में 3-कलरिंग के लिए वितरित एल्गोरिदम: ओ ({{log-star}}एन) तुल्यकालिक संचार दौर।<ref>{{cite journal
+*एन-चक्र को 3-रंग देने के लिए रिचर्ड कोल और उजी विश्किन का वितरित एल्गोरिदम: ''O''(log* ''n'') सिंक्रोनस संचार राउंड।<ref>{{cite journal
   | last1 = Cole | first1 = Richard | author1-link = Richard J. Cole
   | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin
@@ Line 57: / Line 59: @@
   | year = 1986| doi-access = free
   }}</ref>
-पुनरावृत्त लघुगणक अत्यंत धीमी गति से बढ़ता है, लघुगणक की तुलना में बहुत धीमी गति से। एन के सभी मूल्यों के लिए अभ्यास में कार्यान्वित एल्गोरिदम के चलने के समय की गणना करने के लिए प्रासंगिक (यानी, एन ≤ 2<sup>65536</sup>, जो ज्ञात ब्रह्मांड में परमाणुओं की अनुमानित संख्या से कहीं अधिक है), आधार 2 के साथ पुनरावृत्त लघुगणक का मान 5 से अधिक नहीं है।
+पुनरावृत्त लघुगणक अत्यंत धीमी गति से बढ़ता है, लघुगणक की तुलना में बहुत धीमी गति से। n के सभी मानो के लिए अभ्यास में कार्यान्वित एल्गोरिदम के चलने के समय की गणना करने के लिए प्रासंगिक (अथार्त, n ≤ 2<sup>65536</sup>, जो ज्ञात ब्रह्मांड में परमाणुओं की अनुमानित संख्या से कहीं अधिक है), आधार 2 के साथ पुनरावृत्त लघुगणक का मान 5 से अधिक नहीं है।
 {|class=wikitable
-|+The base-2 iterated logarithm
+|+आधार-2 पुनरावृत्त लघुगणक
 ! ''x'' !! {{lg-star}}&nbsp;''x''
 |-
@@ Line 75: / Line 77: @@
 | {{open-closed|65536, 2<sup>65536</sup>}} || 5
 |}
-उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। दरअसल, जटिलता सिद्धांत में आमतौर पर उपयोग किया जाने वाला एकमात्र कार्य जो धीरे-धीरे बढ़ता है वह है एकरमेन फ़ंक्शन # उलटा।
+उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। वास्तव में, जटिलता सिद्धांत में सामान्यतः उपयोग किया जाने वाला एकमात्र फलन जो अधिक धीरे-धीरे बढ़ता है वह उलटा एकरमैन फलन है।
 == अन्य अनुप्रयोग ==
-पुनरावृत्त लघुगणक [[सममित स्तर-सूचकांक अंकगणित]] में प्रयुक्त सामान्यीकृत लघुगणक फलन से निकटता से संबंधित है। किसी संख्या की योगात्मक दृढ़ता, जितनी बार किसी को उसके [[डिजिटल जड़]] तक पहुँचने से पहले संख्या को उसके अंकों के योग से बदलना चाहिए, वह है <math>O(\log^* n)</math>.
+पुनरावृत्त लघुगणक सममित स्तर-सूचकांक अंकगणित में उपयोग किए जाने वाले सामान्यीकृत लघुगणक फलन से निकटता से संबंधित है। किसी संख्या की योगात्मक दृढ़ता, किसी को उसके डिजिटल रूट तक पहुंचने से पहले संख्या को उसके अंकों के योग से बदलने की संख्या <math>O(\log^* n)</math> है।
-कम्प्यूटेशनल जटिलता सिद्धांत में, संथानम<ref>{{cite conference
+कम्प्यूटेशनल जटिलता सिद्धांत में, संथानम <ref>{{cite conference
   | last = Santhanam | first = Rahul
   | contribution = On separators, segregators and time versus space
@@ Line 89: / Line 93: @@
   | title = Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001
   | title-link = Computational Complexity Conference
-  | year = 2001}}</ref> दिखाता है कि [[कम्प्यूटेशनल संसाधन]] [[DTIME]] - एक [[ट्यूरिंग मशीन]] के लिए [[समय]] की जटिलता - और NTIME - एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] के लिए गणना समय - अलग-अलग हैं <math>n\sqrt{\log^*n}.</math>
+  | year = 2001}}</ref> दर्शाता है कि कम्प्यूटेशनल संसाधन डीटाइम - एक नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - और एनटाइम- एक गैर-नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - <math>n\sqrt{\log^*n}.</math> तक भिन्न हैं।
 ==संदर्भ==
 {{reflist}}

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 20:15, 10 July 2023

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

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 20:15, 10 July 2023

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

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories