Traversing the Linked List (In Hindi) | लिंक सूची Traversing

लिंक सूची Traversing

हम ये मान लेते हैं की head पॉइंटर फर्स्ट नोड को पॉइंट कर रहा है। हमे traverse करने के लिए निम्नलिखित कदम लेने होंगे :-

1. Follow the pointers.
2. Display the contents of the nodes (or count) as they are traversed.
3. Stop when the next pointer points to NULL.

listLength() फंक्शन लिंक्ड लिस्ट में कितने नोड्स हैं उन्हें बताता है।
यही फंक्शन लिंक्ड लिस्ट प्रिंट करने के लिए  भी  इस्सतमल में आ सकता है।

def listLength(self):
   current = self.head
   count = 0
   while current != None:
      count = count + 1
      current = current.getNext()
   return count

Time Complexity: O(n)
Space Complexity: O(1)

Comparison of Linked Lists with Arrays and Dynamic Arrays (In HINDI)

ऐरे और डायनामिक ऐरे के साथ लिंक सूचियों की तुलना

लिंक सूचियों के साथ मुद्दे (नुकसान)
लिंक सूचियों में मुद्दों का एक नंबर रहे हैं। लिंक सूचियों के मुख्य नुकसान व्यक्ति तक पहुँच समय है तत्वों। ऐरे यह सरणी में किसी भी तत्व का उपयोग करने के लिए ओ (1) लेता है, जिसका मतलब है यादृच्छिक अभिगम है। लिंक सूचियों सबसे खराब स्थिति में सूची में एक तत्व के लिए उपयोग करने के लिए O (एन) लेता है। उपयोग समय में सरणियों का एक और लाभ यह है स्मृति में spacial इलाके। सारणियों स्मृति से सटे ब्लॉक के रूप में परिभाषित कर रहे हैं, और इसलिए किसी भी सरणी तत्व हो जाएगा शारीरिक रूप से अपने पड़ोसियों के पास। यह बहुत आधुनिक सीपीयू कैशिंग तरीकों से फायदा होता है।

लिंक सूचियों के लाभ
लिंक सूचियों के फायदे और नुकसान दोनों है। लिंक सूचियों का लाभ का विस्तार किया जा सकता है लगातार समय में। एक सरणी (Array) बनाने के लिए हम तत्वों की एक निश्चित संख्या के लिए स्मृति आवंटन करना चाहिए। अधिक तत्वों (element) जोड़ने के लिए हमे एक नई सरणी (Array) बनाना होगा और नई सरणी में पुराने सरणी (array) नकल करना चाहिए। यह ले जा सकते हैं काफी सारा समय। हम शुरू में अंतरिक्ष के बहुत सारे आवंटन से रोक सकते हैं, लेकिन फिर आप की जरूरत से ज्यादा का आवंटन हो सकता है और स्मृति बर्बाद कर रहे। एक लिंक सूची के साथ हम आवंटित सिर्फ एक तत्व के लिए अंतरिक्ष के साथ शुरू कर सकते हैं।

धन्यवाद

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) फिर से वही है। 

Interactive mode in python program (in HINDI) | पाइथन प्रोग्राम में इंटरैक्टिव मोड।

हम जानते हैं की पाइथन एक प्रोग्रामिंग भाषा है, लेकिन यह नहीं जानता कि प्रोग्राम क्या है? इसलिए, प्रोग्राम को समझने के लिए हम पाइथन का इस्सतमल करेंगे।
पाइथन शैल ( python shell )दो तरीकों से किया जा सकता है, अर्थात।, इंटरैक्टिव मोड (interactive mode) और स्क्रिप्ट मोड( script mode )। जहाँ नाम का सुझाव के रूप में इंटरएक्टिव मोड, हमें ओएस (OS) के साथ बातचीत करने के लिए अनुमति देता है;
स्क्रिप्ट मोड (script mode) हमें पाइथन सोर्स फाइल बनाने में मदत करता है। अब, हम पहली इंटरैक्टिव मोड के साथ शुरू होगा।

इंटरैक्टिव मोड

>>>print “How are you?”
How are you?

पाइथन की प्रतिक्रिया जान लेते है। हम निम्नलिखित स्टेटमेंट लिख कर प्रतिक्रिया की जाँच कर सकते हैं।
i)print 5+7
ii) 5+7
iii) 6*250/9
iv) print 5-7

कुछ उदाहरण दिए गए हैं नीचे

अब हम एक छोटे से कोड लिखने के लिए अच्छा कर रहे हैं
^ D (Ctrl + D) या quit() दुभाषिया (interpreter) छोड़ने के लिए प्रयोग किया जाता है।
^ F6 खोल ( shell ) पुनः आरंभ करेगा।

अगर हमे बड़े कोड लिखने हैं तो हमे shell मोड का इस्सतमल करना पड़े गा। 

धन्यवाद

Radix Sort in Python (in HINDI) | पाइथन में रेडिक्स सॉर्ट।

कथन:
प्राकृतिक क्रम में उन्हें पुनर्व्यवस्थित, पूर्णांकों की एक अव्यवस्थित सूची को देखते हुए।

नमूना इनपुट: [534, 246, 933, 127, 277, 321, 454, 565, 220]

नमूना आउटपुट: [127, 220, 246, 277, 321, 454, 534, 565, 933]

:समाधान की समय जटिलता (Time Complexity)
सबसे अच्छा मामले ओ (के एन) O(kn); औसत के मामले ओ (के एन)O(kn); सबसे खराब स्थिति हे (के .एन.)O(kn),

जहाँ पर के (k) सबसे लम्बे नंबर की लम्बाई है।

k lon(n) "क लॉग (एन)" से अधिक है तो एक nlog (एन) एल्गोरिथ्म एक बेहतर फिट होगा। हकीकत में हम हमेशा मूलांक बदल सकते हैं

दृष्टिकोण:
मूलांक तरह, प्रकार और बाल्टी प्रकार की गिनती की तरह, आधारित एक पूर्णांक है
इनपुट सरणी के मूल्यों यानी # एल्गोरिथ्म (माना जाता है पूर्णांकों)। इसलिए मूलांक तरह सबसे तेजी से छँटाई एल्गोरिदम के बीच है चारों ओर, सिद्धांत में। मूलांक तरह के लिए विशेष भेद है
यह प्रत्येक सिफर (यानी अंकों) के लिए एक बाल्टी बनाता है कि #; जैसे की, प्रकार बाल्टी के लिए भी इसी तरह, मूलांक तरह प्रत्येक बाल्टी होना चाहिए अलग चाबियाँ स्वीकार कर सकते हैं कि # उगने वाली दाढ़ी सूची।
दशमलव मूल्यों के लिए , बकेट की संख्या दशमलव के रूप में 10 है, प्रणाली 10 अंकों के / Cyphers (यानी 0,1,2,3,4,5,6,7,8,9) है। फिर चाबियाँ लगातार महत्वपूर्ण अंक के अनुसार क्रमबद्ध हैं।

प्रोग्राम के नीचे लिखा है :-

def RadixSort(A):
    RADIX = 10
    maxLength = False
    tmp , placement = -1, 1

    while not maxLength:
        maxLength = True
        buckets = [list() for _ in range(RADIX)]
        for  i in A:
            tmp = i / placement
            buckets[tmp % RADIX].append(i)
            if maxLength and tmp > 0:
                maxLength = False

        a = 0
        for b in range(RADIX):
            buck = buckets[b]
            for i in buck:
                A[a] = i
                a += 1
    # move to next digit
    placement *= RADIX
    return A
A = [534, 246, 933, 127, 277, 321, 454, 565, 220]
print(RadixSort(A))

यही प्रोग्राम अगर आप सभी प्रकार के इनपुट के लिए लिखना चाहते हैं तो वह भी निचे लिखा गया है।

def RadixSort(A):
    RADIX = 10
    maxLength = False
    tmp , placement = -1, 1

    while not maxLength:
        maxLength = True
        buckets = [list() for _ in range(RADIX)]
        for  i in A:
            tmp = i / placement
            buckets[tmp % RADIX].append(i)
            if maxLength and tmp > 0:
                maxLength = False

        a = 0
        for b in range(RADIX):
            buck = buckets[b]
            for i in buck:
                A[a] = i
                a += 1
    # move to next digit
    placement *= RADIX
    return A
A = []
n = input("Enter the numebr of elements you want to sort : ")
print("Enter the numbers : \n")
for i in range(0, n):
    num = int(input())
    A.append(num)
print(RadixSort(A))

धन्यवाद

Time Complexity involving if, elif and else condition in Python Program (in HINDI)

पाइथन प्रोग्राम की समय जटिलता ( टाइम कोम्प्लेक्सिटी ) जिनमे if, elif, अथवा else कंडीशंस इस्सतमल किया गया है।

निचे कुछ उदाहरण मैंने लिख रखे है। 

पहला उद्धरण

def SimpleIfCondition(n):
    i = n
    if i == 0: 
        i = i + 1
    print i

इस प्रोग्राम की समय जटिलता ( टाइम कोम्प्लेक्सिटी ) ओ(1) यानी  "O(1)" है।

विवरण / व्याख्या
हम मान लेते हैं की असाइनमेंट (assignment) ऑपरेटर केवल एक यूनिट समय लेता है। 
साथ ही में अगर कोई कंडीशनल if , elif अथवा else कंडीशन है तो वह भी एक यूनिट समय लेता है। 

अब हम साफ देख सकते हैं की ४ (4) स्टेटमेंट निष्पादित (execute) होंगे अथार्त हम इस फंक्शन की समय जटिलता (time complexity) को O(4) बोल सकते है जो की O(1) के बराबर है।
यह प्रोग्राम कांस्टेंट समय लेता है। 

दूसरा उद्धरण 

def IfElseCondition(n):
    i = n
    if i == 0: 
        i = i + 1
    elif i == 1:
        i += 2    
    print i  
    
# O(1)

यह उदाहरण भी पिछले उदाहरण की तरह है।
इस की टाइम कोम्प्लेक्सिटी भी O(1) ही है।
इस प्रोग्राम के लिए स्पष्टीकरण की कोई जरूरत नहीं है।

कुछ ऐसे प्रोग्राम जिनकी टाइम कोम्प्लेक्सिटी O(n) है। 

तीसरा उद्धरण 

# O(n)    
def testFunction(n):
    for j in range(1,n):
            print j           

इस फंक्शन में फॉर लूप ऍन(n) बार चल रहा है और हर बार j की वैल्यू प्रिंट कर रहा है। अर्थार्त इस फंक्शन की टाइम कोम्प्लेक्सिटी O(n) है। 

चौथा उद्धरण  

# O(n)
def IfElseCondition2(n):
    i = n
    if i > 0: 
        for j in range(1,n):
            print j
    elif i < 0:
        i += 2    
    print i   

अगर हम इस फंक्शन में ऍन (n) की वैल्यू 0 से बड़ी डालते है तो इस प्रोग्राम की टाइम कोम्प्लेक्सिटी भी हो O(n) जाएगी। 
जैसा की हम जानते हैं  प्रोग्राम की सबसे खराब मामले की प्रतिनिधिनित्वा करता है। इसीलिए इस का टाइम कोम्प्लेक्सिटी O(n) है। 

पांचवा उद्धरण 

# O(n^2): Note that if testFunction is executed always
def IfElseCondition3(n):
    i = n
    if testFunction(n) > 0: 
        for j in range(1,n):
            print j
    elif i < 0:
        i += 2    
    print i   

नोट है कि अगर हमेशा चलता है तो इस्सकी टाइम कोम्प्लेक्सिटी ओ(n^2) हो जाएगी। 

आप को किसी भी प्रकार का संदेह है तो इस पोस्ट की टिप्पणी अनुभाग में पूछ सकते है। 

धन्यवाद