Python Program with time complexity of log (n) | पाइथन प्रोग्राम जिनकी टाइम कोम्प्लेक्सिटी log n है।

नमस्कार आपका यहाँ स्वागत है।
आज हम कुछ ऐसे पाइथन प्रोग्राम देखेंगे जिनकी टाइम कोम्प्लेक्सिटी ( time complexity ) लोग न ( log n ) है।
और साथ ही में हम यह भी बतायेँगे की इन पाइथन प्रोग्राम्स की time complexity (समय जटिलता ) log n क्यों है।

पहला प्रोग्राम :-

def Logarithms(n):
    i = n
    while i >= 1: 
        i = i // 2
        print i 

Logarithms(100)
# time complexity is log2(n)

कृपया ध्यान दें की logarithm (लघुगणक) का बेस २ है .

अब हम इसकी टाइम कोम्प्लेक्सिटी निकलते हैं।

आप // ऑपरेटर के कुछ उदाहरण पर विचार कर सकते हैं

5//2 = 2
6//2 = 3
11//2 = 5

यह बहुत जटिल (कठिन) नहीं है, हालांकि, यह देखने का एक और अधिक गणितीय तरीका है।
सवाल यह है की  आप कितनी बार आप 2 से एन (n) को विभाजित कर सकते हैं ताकि आपको १ मिल जाये , है ना?
ऊपर दिए गए बयान अनिवार्य रूप से आपको यह बता रहे हैं की  आप (2 से विभाजित)  करते रहें जब तक आपका अंक १ से बड़ा है।

1 = N / 2^x

2^x से गुणा:

2^x = N
log2(2^x) = log2 N
x * log2(2) = log2 N
x * 1 = log2 N

x = log2 N

ग्राफ : y = log2(n)

दूसरा प्रोग्राम :-

def Logarithms2(n):
    i = 1
    while i <= n: 
        i = i * 2
        print i 

Logarithms(100)

इस प्रोग्राम का काम ऊपर वाले प्रोग्राम के विपरीत है।

यहां हालत गलत होंगे जब 2^x > N हो जायेगा।
अर्थात्

2^x = N
log2(2^x) = log2 N
x * log2(2) = log2 N
x * 1 = log2 N

x = log2 N

हम स्पष्ट रूप से समय जटिलता (time complexity) फिर से वही है।