पुनरावृत्त लघुगणक

For the theorem in probability theory, see Law of the iterated logarithm.

कंप्यूटर विज्ञान में, का पुनरावृत्त लघुगणक $n$, लिखा हुआ log* $n$ (आमतौर पर लॉग स्टार पढ़ा जाता है), परिणाम से कम या उसके बराबर होने से पहले लघुगणक फ़ंक्शन को पुनरावृति लागू करने की संख्या है $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$

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

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

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

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

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

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

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

• यूक्लिडियन न्यूनतम फैले हुए पेड़ को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाना: यादृच्छिक बिग-ओ नोटेशन (एनlog*एन) समय।
• पूर्णांक गुणन के लिए फ्यूरर का एल्गोरिदम: O(n log n 2^{हे(lg*एन)</सुप>).}
• अनुमानित अधिकतम ढूँढना (तत्व कम से कम माध्यिका जितना बड़ा): lg*एन - 4 से lg*n + 2 समानांतर संचालन।
• रिचर्ड कोल और उजी विस्किन का ग्राफ कलरिंग # समानांतर और वितरित एल्गोरिदम | एन-साइकिल में 3-कलरिंग के लिए वितरित एल्गोरिदम: ओ (log*एन) तुल्यकालिक संचार दौर।

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

The base-2 iterated logarithm

x	lg* x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 265536]	5

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

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

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

कम्प्यूटेशनल जटिलता सिद्धांत में, संथानम दिखाता है कि कम्प्यूटेशनल संसाधन DTIME - एक ट्यूरिंग मशीन के लिए समय की जटिलता - और NTIME - एक गैर-नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - अलग-अलग हैं $n{\sqrt {\log ^{*}n}}.$