c - जबकि लूप समय जटिलता हे(लॉगन)

आप n से पहले (या उससे कम) 1 के बराबर होने की गणना करनी चाहते हैं

यदि आप k के पुनरावृत्तियों की संख्या को कॉल करते हैं तो आप हल करना चाहते हैं

n * 0.999 ^ के = 1

यह इस प्रकार चलता है

n * 0.999 ^ के = 1

0.999 ^ के = 1 / एन

लॉग (0.999 ^ के) = लॉग (1 / एन)

k * लॉग (0.9 99) = -log (n)

k = -log (n) / लॉग (0.9 99)

k = (-1 / log (0.999)) * लॉग (एन)

बड़े-ओ के लिए हम केवल "बड़ी तस्वीर" की परवाह करते हैं, इसलिए हम स्थिरांक को दूर कर देते हैं। यहां log(0.999) एक नकारात्मक स्थिरांक है (-1 / लॉग (0.9 99)) एक सकारात्मक स्थिरांक है जिसे हम "फेंक" कर सकते हैं, अर्थात् 1 पर सेट। तो हम मिलते हैं:

कश्मीर ~ लॉग (एन)

तो कोड ओ (लॉगन) है

इस से आप यह भी देख सकते हैं कि निरंतर (यानी आपके उदाहरण में 0.9 99) बड़ा-ओ गणना के लिए कोई फर्क नहीं पड़ता है 0 से कम और 1 से कम के सभी निरंतर मानों का परिणाम ओ (लॉगन) होगा

कल्पना कीजिए कि कोड निम्नानुसार थे:

double n;
/* ... */
while (n>1) {
     n*=0.5;
}

यह देखने के लिए सहज ज्ञान युक्त होना चाहिए कि यह हे (लॉगन) क्या है, मैं आशा करता हूं।

जब आप 0.999 से गुणा करते हैं, तो यह एक स्थिर कारक द्वारा धीमा हो जाता है, लेकिन निश्चित रूप से जटिलता अभी भी हे (लॉगन) के रूप में लिखी जाती है