routing algorithm एक ऐसी प्रक्रिया है जो डेटा पैकेट को स्रोत से गंतव्य तक स्थानांतरित करने के लिए मार्ग या पथ निर्धारित करती है। वे इंटरनेट यातायात को कुशलतापूर्वक निर्देशित करने में मदद करते हैं। डेटा पैकेट अपने स्रोत को छोड़ने के बाद, यह अपने गंतव्य तक पहुंचने के लिए कई अलग-अलग रास्तों में से चुन सकता है।  routing algorithm गणितीय रूप से सर्वोत्तम पथ की गणना करता है, अर्थात "न्यूनतम - लागत पथ" जिसके माध्यम से पैकेट को रूट किया जा सकता है।

 Routing algorithm in Hindi & it's type

Routing algorithm in Hindi

routing algorithm को मोटे तौर पर दो प्रकारों में वर्गीकृत किया जा सकता है, adaptive और nonadaptive routing algorithms उन्हें आगे और वर्गीकृत किया जा सकता है जैसा कि निम्नलिखित आरेख में दिखाया गया है -

Adaptive Routing Algorithms in Hindi

Adaptive Routing Algorithms, जिसे डायनेमिक रूटिंग एल्गोरिदम के रूप में भी जाना जाता है, नेटवर्क स्थितियों के आधार पर गतिशील रूप से रूटिंग निर्णय लेता है। यह नेटवर्क ट्रैफिक और टोपोलॉजी के आधार पर रूटिंग टेबल का निर्माण करता है। वे हॉप गिनती, पारगमन समय और दूरी के आधार पर अनुकूलित मार्ग की गणना करने का प्रयास करते हैं।

Adaptive Routing Algorithms के तीन लोकप्रिय प्रकार हैं -

• Centralized algorithm − यह नेटवर्क के बारे में वैश्विक ज्ञान का उपयोग करके स्रोत और गंतव्य नोड्स के बीच कम से कम लागत वाला रास्ता खोजता है। इसलिए, इसे ग्लोबल रूटिंग एल्गोरिथम के रूप में भी जाना जाता है।

• Isolated algorithm − यह एल्गोरिथम अन्य नोड्स से जानकारी एकत्र करने के बजाय स्थानीय जानकारी का उपयोग करके रूटिंग जानकारी प्राप्त करता है।

• Distributed algorithm − यह एक विकेन्द्रीकृत एल्गोरिथम है जो वितरित तरीके से स्रोत और गंतव्य के बीच कम से कम लागत वाले पथ की गणना करता है।

Non – Adaptive Routing Algorithms in Hindi

Non – Adaptive Routing Algorithms, जिसे स्टेटिक रूटिंग एल्गोरिदम (static routing algorithms)के रूप में भी जाना जाता है, एक स्थिर रूटिंग टेबल का निर्माण करता है ताकि यह निर्धारित किया जा सके कि पैकेट को किस रास्ते से भेजा जाना है। नेटवर्क बूट होने पर राउटर में संग्रहीत रूटिंग जानकारी के आधार पर स्थिर रूटिंग टेबल का निर्माण किया जाता है।

दो प्रकार के Non – Adaptive Routing Algorithms हैं -

• Flooding − बाढ़ में, जब एक डेटा पैकेट राउटर पर आता है, तो इसे सभी आउटगोइंग लिंक पर भेजा जाता है, सिवाय इसके कि जिस पर वह आया है। बाढ़ अनियंत्रित, नियंत्रित या चयनात्मक बाढ़ हो सकती है।

• Random walks − यह एक संभाव्य एल्गोरिथम है जहां राउटर द्वारा अपने किसी एक पड़ोसी को डेटा पैकेट बेतरतीब ढंग से भेजा जाता है।

 विभिन्न प्रोग्रामिंग समस्याओं के लिए स्ट्रिंग्स को अनिवार्य रूप से सबसे महत्वपूर्ण और सामान्य विषयों के रूप में देखा जा सकता है। स्ट्रिंग प्रसंस्करण में कई वास्तविक दुनिया अनुप्रयोग होते हैं, जैसे:

• Search Engines
• Genome Analysis
• Data Analytics

पाठ्य सामग्री के रूप में हमारे सामने प्रस्तुत सभी सामग्री को केवल  strings के अलावा और कुछ भी नहीं देखा जा सकता है।

trie data structure In Hindi

Tries एक अत्यंत विशेष और उपयोगी डेटा-संरचना है जो एक स्ट्रिंग के उपसर्ग पर आधारित हैं। उनका उपयोग डेटा के “Retrieval” का प्रतिनिधित्व करने के लिए किया जाता है और इस प्रकार Trie नाम।

prefix trie : What is prefix:

एक स्ट्रिंग का उपसर्ग कुछ भी नहीं है लेकिन (n, n<=mod(S)) किसी भी अक्षर को एक स्ट्रिंग की शुरुआत से सख्ती से शुरुआत माना जा सकता है। उदाहरण के लिए, शब्द “abacaba” में निम्नलिखित उपसर्ग हैं:

a
ab
aba
abac
abaca
abacab

Trie एक विशेष Data structure है जिसका उपयोग स्ट्रिंग्स को स्टोर करने के लिए किया जाता है जिसे ग्राफ की तरह देखा जा सकता है। यह नोड्स और किनारों के होते हैं। प्रत्येक नोड में अधिकतम 26 बच्चे होते हैं और प्रत्येक माता-पिता नोड को अपने बच्चों से जोड़ते हैं। ये 26 पॉइंटर्स अंग्रेजी वर्णमाला के 26 अक्षरों में से प्रत्येक के लिए पॉइंटर्स के अलावा और कुछ नहीं हैं। हर किनारे के लिए एक अलग एज बनाए रखा गया है।

एक trie data structure में उनके prefix के आधार पर स्ट्रिंग्स को ऊपर से नीचे तरीके से संग्रहीत किया जाता है। लंबाई 1 के सभी उपसर्गों को स्तर 1 तक संग्रहीत किया जाता है, लंबाई 2 के सभी prefixes को स्तर 2 और इसी तरह तक हल किया जाता है।

For example For trie data structure, consider the following diagram :- :

trie data structure

अब, कोई सोच रहा होगा कि एकल स्ट्रिंग को संसाधित करने के लिए डेटा संरचना जैसे ट्राई का उपयोग क्यों किया जाए? दरअसल, ट्राई का इस्तेमाल आम तौर पर स्ट्रिंग्स के समूहों पर किया जाता है, न कि एक स्ट्रिंग के बजाय। जब कई तार दिए जाते हैं, तो हम उनके आधार पर कई तरह की समस्याओं को हल कर सकते हैं। 

उदाहरण के लिए, एक अंग्रेजी शब्दकोश और एक स्ट्रिंग पर विचार करें, स्ट्रिंग से मेल खाते शब्दकोश स्ट्रिंग (s)से अधिकतम लंबाई का उपसर्ग खोजें। एक Naive approach का उपयोग करके इस समस्या को हल करने के लिए हमें दिए गए स्ट्रिंग के उपसर्ग को शब्दकोश में हर दूसरे शब्द के उपसर्ग के साथ मेल करना होगा और अधिकतम नोट करना होगा। यह एक  expensive प्रक्रिया है जिस पर समय लगेगा। trie in data structure इस समस्या को अधिक कुशल तरीके से हल कर सकती है।

प्रत्येक प्रकार की क्वेरी को संसाधित करने से पहले, जहां हमें सबसे लंबे उपसर्ग की लंबाई की खोज करने की आवश्यकता है, हमें पहले सभी मौजूदा शब्दों को शब्दकोश में जोड़ना होगा। एक trie में एक विशेष नोड होता है जिसे रूट नोड कहा जाता है। इस नोड में कोई आवक नहीं है। इसमें वर्णमाला के प्रत्येक अक्षर के लिए केवल 26 आउटगोइंग ईडीएफ शामिल हैं और यह ट्राइ का मूल है।

तो,  Trie में किसी भी स्ट्रिंग का insertion रूट नोड से शुरू होता है। लंबाई एक के सभी उपसर्ग रूट नोड के प्रत्यक्ष बच्चे हैं। इसके अलावा, लंबाई 2 के सभी उपसर्ग लेवल एक पर मौजूद नोड्स के बच्चे बन जाते हैं।

टायर में स्ट्रिंग डालने के लिए  pseudo code निम्नानुसार दिखेगा:

trie data structure

 इस ट्यूटोरियल में, आप सीखेंगे कि b tree in data structure क्या है। साथ ही, आपको C, C ++, Java और पायथन में B - Tree पर सर्च ऑपरेशन के काम के उदाहरण मिलेंगे।

b tree in data structure एक विशेष प्रकार का स्व-संतुलन खोज Tree है जिसमें प्रत्येक नोड में एक से अधिक कुंजी हो सकती हैं और दो से अधिक Child हो सकते हैं। यह b search tree का एक सामान्यीकृत रूप है।

इसे ऊंचाई वाले संतुलित m-way tree के रूप में भी जाना जाता है।

B tree in hindi

Why b tree in data structure?

हार्ड-डिस्क की तरह भौतिक भंडारण मीडिया तक पहुँचने में कम समय की आवश्यकता के बढ़ने के साथ b tree की आवश्यकता उत्पन्न हुई। 

द्वितीयक भंडारण उपकरण एक बड़ी क्षमता के साथ धीमे हैं। इस तरह की डेटा संरचनाओं की आवश्यकता थी जो डिस्क एक्सेस को कम करती हैं।

अन्य डेटा संरचनाएं जैसे कि एक b search tree, एवल ट्री, रेड-ब्लैक ट्री, आदि एक नोड में केवल एक कुंजी स्टोर कर सकते हैं। 

यदि आपको बड़ी संख्या में चाबियाँ जमा करनी हैं, तो ऐसे पेड़ों की ऊंचाई बहुत बड़ी हो जाती है और पहुंच का समय बढ़ जाता है।

हालांकि, b tree एक ही नोड में कई चाबियाँ संग्रहीत कर सकते हैं और कई बच्चे नोड्स हो सकते हैं। यह तेजी से डिस्क एक्सेस की अनुमति देते हुए ऊंचाई को कम करता है।

B-tree in Hindi and it's Properties

•     प्रत्येक नोड x के लिए, कुंजियाँ बढ़ते क्रम में संग्रहीत की जाती हैं।
•     प्रत्येक नोड में, बूलियन मान x.leaf होता है जो x पत्ती होने पर सत्य होता है।

•     यदि n पेड़ का क्रम है, तो प्रत्येक आंतरिक नोड में प्रत्येक बच्चे के लिए एक सूचक के साथ अधिकांश n - 1 कुंजी हो सकती हैं।

•     रूट को छोड़कर प्रत्येक नोड में अधिकांश n बच्चे और कम से कम n / 2 बच्चे हो सकते हैं।

•     सभी पत्तियों में एक ही गहराई (यानी पेड़ की ऊंचाई-एच) होती है।
•     मूल में कम से कम 2 बच्चे हैं और इसमें न्यूनतम 1 कुंजी है।

•     यदि n-1 है, तो ऊँचाई h और न्यूनतम डिग्री t, 2, h + logt (n + 1) / 2 के किसी भी n-key B- वृक्ष के लिए।

Operations b tree in data structure in Hindi

Learn Searching in B tree in Hindi

बी-ट्री में एक तत्व की खोज करना Binary Search Tree में एक तत्व की खोज का सामान्यीकृत रूप है। निम्न चरणों का पालन किया जाता है।

•     रूट नोड से शुरू, नोड की पहली कुंजी के साथ तुलना करें।
•     यदि k = the first key of the node, तो नोड और इंडेक्स वापस करें।
•     यदि k.leaf = true है, तो NULL (यानी नहीं मिला) लौटें।
•     यदि k < the first key of the root node, तो इस कुंजी के बाएं बच्चे को पुनरावर्ती खोजें।
•     यदि वर्तमान नोड और k > the first key में एक से अधिक कुंजी है, तो नोड में अगली कुंजी के साथ तुलना करें।
•     यदि k < next key तो इस कुंजी के बाएं बच्चे को खोजें (यानी। k पहली और दूसरी कुंजियों के बीच स्थित है)।
•     और, कुंजी के सही बच्चे को खोजें।
•     पत्ती तक पहुंचने तक चरण 1 से 4 दोहराएं।

Searching b tree example

•     हमें डिग्री 3 के नीचे के Tree में k= 17 की खोज करनी चाहिए।

B-tree in hindi

• k रूट में नहीं मिला है, इसलिए इसे रूट की के साथ तुलना करें।

b tree insertion

• K> 11 के बाद से, रूट नोड के सही बच्चे पर जाएं।

b tree example

• K की तुलना 16 से करें। k> 16 के बाद से k की तुलना अगली कुंजी 18 से करें।

B tree in hindi

• K <18 के बाद से, k 16 और 18 के बीच स्थित है। 16 के दाहिने बच्चे या 18 के बाएं बच्चे में खोजें।

b tree in data structure

• k पाया जाता है।

b tree example

Algorithm For B tree in Hindi

BtreeSearch(x, k)
 i = 1
 while i ≤ n[x] and k ≥ keyi[x]        // n[x] means number of keys in x node
    do i = i + 1
if i  n[x] and k = keyi[x]
    then return (x, i)
if leaf [x]
    then return NIL
else
    return BtreeSearch(ci[x], k)

B tree example program in c

#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct BTreeNode {
  int val[MAX + 1], count;
  struct BTreeNode *link[MAX + 1];
};

struct BTreeNode *root;

// Create a node
struct BTreeNode *createNode(int val, struct BTreeNode *child) {
  struct BTreeNode *newNode;
  newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
  newNode->val[1] = val;
  newNode->count = 1;
  newNode->link[0] = root;
  newNode->link[1] = child;
  return newNode;
}

// Insert node
void insertNode(int val, int pos, struct BTreeNode *node,
        struct BTreeNode *child) {
  int j = node->count;
  while (j > pos) {
    node->val[j + 1] = node->val[j];
    node->link[j + 1] = node->link[j];
    j--;
  }
  node->val[j + 1] = val;
  node->link[j + 1] = child;
  node->count++;
}

// Split node
void splitNode(int val, int *pval, int pos, struct BTreeNode *node,
         struct BTreeNode *child, struct BTreeNode **newNode) {
  int median, j;

  if (pos > MIN)
    median = MIN + 1;
  else
    median = MIN;

  *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
  j = median + 1;
  while (j <= MAX) {
    (*newNode)->val[j - median] = node->val[j];
    (*newNode)->link[j - median] = node->link[j];
    j++;
  }
  node->count = median;
  (*newNode)->count = MAX - median;

  if (pos <= MIN) {
    insertNode(val, pos, node, child);
  } else {
    insertNode(val, pos - median, *newNode, child);
  }
  *pval = node->val[node->count];
  (*newNode)->link[0] = node->link[node->count];
  node->count--;
}

// Set the value
int setValue(int val, int *pval,
           struct BTreeNode *node, struct BTreeNode **child) {
  int pos;
  if (!node) {
    *pval = val;
    *child = NULL;
    return 1;
  }

  if (val < node->val[1]) {
    pos = 0;
  } else {
    for (pos = node->count;
       (val < node->val[pos] && pos > 1); pos--)
      ;
    if (val == node->val[pos]) {
      printf("Duplicates are not permitted\n");
      return 0;
    }
  }
  if (setValue(val, pval, node->link[pos], child)) {
    if (node->count < MAX) {
      insertNode(*pval, pos, node, *child);
    } else {
      splitNode(*pval, pval, pos, node, *child, child);
      return 1;
    }
  }
  return 0;
}

// Insert the value
void insert(int val) {
  int flag, i;
  struct BTreeNode *child;

  flag = setValue(val, &i, root, &child);
  if (flag)
    root = createNode(i, child);
}

// Search node
void search(int val, int *pos, struct BTreeNode *myNode) {
  if (!myNode) {
    return;
  }

  if (val < myNode->val[1]) {
    *pos = 0;
  } else {
    for (*pos = myNode->count;
       (val < myNode->val[*pos] && *pos > 1); (*pos)--)
      ;
    if (val == myNode->val[*pos]) {
      printf("%d is found", val);
      return;
    }
  }
  search(val, pos, myNode->link[*pos]);

  return;
}

// Traverse then nodes
void traversal(struct BTreeNode *myNode) {
  int i;
  if (myNode) {
    for (i = 0; i < myNode->count; i++) {
      traversal(myNode->link[i]);
      printf("%d ", myNode->val[i + 1]);
    }
    traversal(myNode->link[i]);
  }
}

int main() {
  int val, ch;

  insert(8);
  insert(9);
  insert(10);
  insert(11);
  insert(15);
  insert(16);
  insert(17);
  insert(18);
  insert(20);
  insert(23);

  traversal(root);

  printf("\n");
  search(11, &ch, root);
}

b tree insertion Operation

•      यदि पेड़ खाली है, तो रूट नोड आवंटित करें और कुंजी डालें।
•      नोड में कुंजियों की अनुमत संख्या को अपडेट करें।
•      सम्मिलन के लिए उपयुक्त नोड खोजें।
•      यदि नोड भरा हुआ है, तो नीचे दिए गए चरणों का पालन करें।
•      तत्वों को बढ़ते क्रम में डालें।
•      अब, इसकी सीमा से अधिक तत्व हैं। तो, मंझला में विभाजित करें।
•      माध्य कुंजी को ऊपर की ओर धकेलें और बाएँ कुंजियों को बाएँ बच्चे के रूप में और दाएँ कुंजियों को दाएँ बच्चे के रूप में बनाएँ।
•      यदि नोड भरा नहीं है, तो नीचे दिए गए चरणों का पालन करें।
•      बढ़ते क्रम में नोड डालें।

b tree insertion Example

आइए नीचे दिए गए चित्रों के साथ सम्मिलन ऑपरेशन को समझते हैं।

सम्मिलित किए जाने वाले तत्व 8, 9, 10, 11, 15, 16, 17, 18, 20, 23 हैं।

b tree example

 b tree insertion Algorithm

BreeInsertion(T, k)
r  root[T]
if n[r] = 2t - 1
    s = AllocateNode()
    root[T] = s
    leaf[s] = FALSE
    n[s] <- 0
    c1[s] <- r
    BtreeSplitChild(s, 1, r)
    BtreeInsertNonFull(s, k)
else BtreeInsertNonFull(r, k)
BtreeInsertNonFull(x, k)
i = n[x]
if leaf[x]
    while i ≥ 1 and k < keyi[x]
        keyi+1 [x] = keyi[x]
        i = i - 1
    keyi+1[x] = k
    n[x] = n[x] + 1
else while i ≥ 1 and k < keyi[x]
        i = i - 1
    i = i + 1
    if n[ci[x]] == 2t - 1
        BtreeSplitChild(x, i, ci[x])
        if k &rt; keyi[x]
            i = i + 1
    BtreeInsertNonFull(ci[x], k)
BtreeSplitChild(x, i)
BtreeSplitChild(x, i, y)
z = AllocateNode()
leaf[z] = leaf[y]
n[z] = t - 1
for j = 1 to t - 1
    keyj[z] = keyj+t[y]
if not leaf [y]
    for j = 1 to t
        cj[z] = cj + t[y]
n[y] = t - 1
for j = n[x] + 1 to i + 1
    cj+1[x] = cj[x]
ci+1[x] = z
for j = n[x] to i
    keyj+1[x] = keyj[x]
keyi[x] = keyt[y]
n[x] = n[x] + 1

 यदि आप एक कुशल प्रोग्रामर हैं तो समय जटिलता एक सामान्य शब्द है (big o notation, small o notation, omega notation) हालाँकि, यदि आपने तब यह सुनिश्चित नहीं किया है कि आप समय जटिलता की गणना को विस्तार से समझने के लिए इस लेख को अच्छी तरह से पढ़ेंगे।

What is Time Complexity in Hindi in Data

 structure?

किसी भी एल्गोरिथ्म / कार्यक्रम का Time Complexity कार्यक्रम को निष्पादित करने के लिए उठाए गए वास्तविक समय का माप नहीं है, बल्कि यह है कि तर्क के प्रत्येक कथन को आवश्यक आउटपुट का उत्पादन करने के लिए निष्पादित किया जाता है।

सरल शब्दों में, यहां हमारा मतलब है। नीचे दिए गए कोड पर विचार करें।

#include <stdio.h>
void main()
{
int i, n = 5;
for (i = 1; i <= n; i++) {
printf("computer in n");
                  } }
                  

इसलिए, एक compiler का उपयोग करके निष्पादित किए गए उपरोक्त कोड ने नीचे आउटपुट दिया है। यदि आप देख सकते हैं, संकलक दिखाता है कि कोड 1.166 सेकेंड में निष्पादित किया गया था और हम में से बहुत से इसे समय जटिलता मानते हैं, लेकिन यह नहीं है।

बल्कि, इस कोड की Time Complexity उस समय पर निर्भर करती है जब कथन निष्पादित होते हैं। यहाँ, लूप के लिए कई बार 'n' संख्या निष्पादित होती है और इसलिए जटिलता O (n) है (हम समझेंगे कि इस लेख के बाद के भाग में O क्या है)

Need to Calculate Time Complexity?

बहुत बार, किसी विशेष समस्या को हल करने के लिए एक से अधिक तरीके हैं और ऐसे मामलों में, आपको सभी में से सबसे कुशल समाधान की पहचान करने में सक्षम होना चाहिए। यह वह जगह है जहां Time Complexity चित्र में आती है। 

समय जटिलता आपको विभिन्न समाधानों के प्रदर्शन की तुलना करने में मदद करती है, इस प्रकार आपको सबसे कुशल समाधान निर्धारित करने में मदद करती है।

Calculate the Time Complexity of an Algorithm?

समय की जटिलता को एसिम्प्टोटिक सूचनाओं के रूप में नीचे दिए गए तीन शब्दों का उपयोग करके व्यक्त किया जा सकता है।

लेकिन ज्यादातर बार, हम Big O Notation in hindi का उपयोग करेंगे क्योंकि यह हमें निष्पादन समय की एक ऊपरी सीमा प्रदान करेगा यानी सबसे खराब स्थिति में निष्पादन का समय। साथ ही, एक एल्गोरिथ्म का चलने का समय एक ही आकार के विभिन्न इनपुट्स के बीच भिन्न हो सकता है, और इसलिए हम सबसे खराब स्थिति पर विचार करते हैं, जो किसी दिए गए आकार के इनपुट के लिए आवश्यक अधिकतम समय है।

समय जटिलता उदाहरण


1)

Big o natation example

Time Complexity Calculation: उपरोक्त दिए गए कार्यक्रम की समय जटिलता हे (1) है, क्योंकि इस कार्यक्रम में केवल असाइनमेंट, अंकगणितीय संचालन शामिल हैं और उन सभी को केवल एक बार निष्पादित किया जाएगा।

2)

Big o natation in hindi

 

Time Complexity Calculation: ऊपर दिए गए स्निपेट में, हमारे पास एक नियंत्रण कथन है जो n समय के लिए निष्पादित होता है। इसके साथ ही हमारे पास असाइनमेंट, अंकगणित और रिटर्न स्टेटमेंट जैसे ऑपरेशन भी हैं। इसलिए, समय जटिलता O (n + 3) है।

N के बड़े मूल्यों के लिए, निरंतर मान नगण्य हो जाते हैं। इसलिए यदि किसी कार्यक्रम में एक नियंत्रण कथन है, तो असाइनमेंट, अंकगणितीय, तार्किक और रिटर्न स्टेटमेंट की जटिलताओं को अनदेखा किया जा सकता है।


इसलिए, ऊपर दिए गए स्निपेट की अंतिम समय जटिलता O (n) है।


3)

big o notation

Time Complexity Calculation:  उपरोक्त स्निपेट में, लूप के लिए पहले और दूसरे को व्यक्तिगत रूप से n बार निष्पादित किया जाता है। तो समय जटिलता n * n = O (n2) के लिए होती है

4)

big o notation

Time Complexity Calculation:  यह बाइनरी खोज का एल्गोरिथ्म है। यह तत्वों के दिए गए सेट को दो हिस्सों में तोड़ता है और फिर एक विशेष तत्व की खोज करता है। इसके अलावा, यह इन दो हिस्सों को आगे के हिस्सों में विभाजित करता रहता है जब तक कि प्रत्येक अलग-अलग तत्व सेट न हो जाए। ऐसे सभी एल्गोरिदम जो तत्वों के पुनरावर्ती विभाजन के सिद्धांत पर काम करते हैं, उनमें ओ (लॉग एन) जटिलता होगी।

Some Real-Time Examples of Time Complexity in

 hindi

उदाहरण 1:

मान लें कि आपकी कक्षा के किसी व्यक्ति ने आपकी पसंदीदा चॉकलेट चुरा ली है। आपको वह चॉकलेट ढूंढनी होगी। नीचे इसे खोजने के कुछ तरीके दिए गए हैं।

•     By asking each and every person in the class, जिसका अर्थ है कि यदि छात्रों की संख्या n है, तो आपको n व्यक्तियों से पूछने की आवश्यकता है। इसलिए, जटिलता हे (एन) है।
•     By asking only one of the students in the class और यदि उसके पास वह चॉकलेट नहीं है, तो उसी व्यक्ति से शेष छात्रों के बारे में पूछें। तो, प्रत्येक व्यक्ति से आप उसी व्यक्ति के बारे में पूछ रहे हैं और शेष व्यक्तियों के बारे में भी। इसलिए, पिछले मामले की तुलना में जटिलता दो बार है। यानी O (n2)। उपर्युक्त दो तरीके कठिन प्रतीत होते हैं।
•     इसलिए, यह कहें कि क्या आप पूरी कक्षा को दो हिस्सों में विभाजित करते हैं और पूछते हैं कि चॉकलेट दाईं ओर है या बाईं ओर। यदि यह दाईं ओर है, तो दाहिनी ओर के लोगों की संख्या को फिर से दो में विभाजित करें और उसी प्रक्रिया को दोहराएं। यहां, पूछताछ की संख्या तेजी से घट रही है। इसलिए, जटिलता हे (लॉग एन)।

Time Complexity Table

big o notation

Time Complexity Chart

आप अब सोच रहे होंगे कि यह बिग ओ नोटेशन आपको विभिन्न एल्गोरिदम की तुलना करने में कैसे मदद कर सकता है और ओ (एन), ओ (एन 2) या ओ (लॉग एन) में से कौन बेहतर है? तो यहां एक चार्ट है जो आपको यह समझने में मदद करेगा कि ऊपर चर्चा की गई समय जटिलताएं कुशल एल्गोरिदम का कौन सा उपाय है।

big notation chart

 

Time Complexity Cheat Sheet of Algorithms

नीचे दिए गए टाइम कॉम्प्लेक्सिटी चीट शीट में कुछ महत्वपूर्ण डेटा संरचना एल्गोरिदम की सबसे अच्छी, औसत और सबसे खराब स्थिति की जटिलताएं हैं

big o notation in hindi