Analyzing Algorithms – The Big O Notation

Analyzing Algorithms – Analysis के लिए हमेंशा Simple Statements Sequence को आधार बनाना चाहिए। सबसे पहले ये Note करें कि Statements की एक Sequence जो कि एक समय में केवल एक बार Execute होती है, उसे Big – O Notation के रूप में Represent करने के लिए हमें केवल O(1) लिखना होता है। क्योंकि एक Statement Execute होने में जितना समय लगाता है सभी Statements Execute होने में उसी अनुपात में समय लगाऐंगे। उदाहरण के लिए यदि किसी Data Item की Size n को किसी Loop द्वारा निम्नानुसार Solve किया जा सकता है-

[code]
//========================================
for(i=0; i<n; i++)
{
  Statement x;
}
//========================================
[/code]

तो इस Loop में Statement x एक O(1) Sequence Statement है इसलिए इस Loop की Time Complexity n O(1) या O(n) होगी।

यदि हमारे पास निम्नानुसार दो Nested Loop हों तो

[code]
//========================================
for(i=0; i<n; i++)
{
  for(j=0; j<n; j++)
  {
    Statement x;
  }
}
//========================================
[/code]

इस स्थिति में Loop i के हर Iteration में Loop j n बार Iterate होता है। यानी ये Nested Loop n * n बार चलेगा इसलिए इस Loop में लगने वाला समय O(n²) के बराबर होगा। निम्न Loop तब तक चलता है जब तक कि n का मान h के मान से बडा या बराबर रहता है-

[code]
//========================================
h = 1;

for(i=0; i<=n; i++)
{
  Statement x;
  h = 2 * h;
}
//========================================
[/code]

इस Loop की Complexity 1 + log n के बराबर है। इसे Big – O Notation के रूप में O( log₂ n ) लिख सकते हैं।

यदि Inner Loop Outer Loop के Index पर निर्भर हो तो Inner Loop में j का मान 0 से n तक चलता है। इस स्थिति में Loop की Complexity निम्नानुसार ज्ञात की जा सकती है-

[code]
//========================================
for(i=0; i<=n; i++)
{
  for(j=0; j<=i; j++)
  {
    Statement x;
  }
}
//========================================

f( j ) =    0 to n         यानी
       =    1 + 2 + 3 + 4 + . . . (n-2) + (n-1) + n   यानी
       =    n * (n + 1) / 2
       =    (n2 + n)/2

[/code]

इस Algorithm की Complexity को Big – O Notation के रूप में हम O( n² ) लिख सकते हैं। यदि हम निम्नानुसार किसी जरूरत के अनुसार Loop चलाते हैं-

[code]
//========================================
h = n;

for(i=0; i<=h; i++)
{
  for(j=0; j<=n; j++)
  {
    Statement x;
  }
  h = h/2;
}
//========================================
[/code]

तो यहां Outer Loop में log₂ n Iterations होंगे और Inner Loop की Complexity O( n ) होगी। इस स्थिति में कुल Complexity O( n log n) होगी। ये Complexity पहले वाले Loop की Complexity की तुलना में अधिक Efficient है।

चलिए, अब हम कुछ Program देखते हैं और उनकी Complexity ज्ञात करने की कोशिश करते हैं। हालांकि इन Programs का वास्तव में कहीं कोई उपयोग नहीं है। ये केवल कुछ Pattern मा= Create करते हैं। इन उदाहरणों में Programs की Efficiency printf() Function के कुल Executions की संख्‍या पर आधारित है जो कि n का फलन है।

[code]
Example 
//========================================
main()
{
int i, j, n;

printf(“Enter the limit of Pattern”);
scanf(“%d”, &n);

for(i=0; i<n; i++)
{
  for(j=0; j<n; j++)
  {
    printf(“%4d, %4d\n”, i, j); 
  }
}

getch();
}
//========================================
[/code]

हम देख सकते हैं कि दोनों Loops में केवल Inner Loop में ही Execute होने वाला Statement है और केवल एक ही Statement है। हमारे Complexity फलन हमें ये बता,गा कि n के फलन के रूप में printf() Function कितनी बार Execute होगा।

इस पूरे Program की Complexity Outer Loop की Complexity के बराबर है क्योंकि यही एक Top Level का Statement है जिसमें printf() Function Use किया गया है। किसी Loop की Complexity को हम निम्न सू= से जान सकते हैं-

Complexity of Loop   =    ( Number of Loop’s Repetitions ) * ( Complexity of each Iteration )

हम मान सकते हैं कि Loop के हर Iteration की Complexity समान है। ऐसा हम Outer Loop के लिए मान सकते हैं इस Loop की Complexity को निम्नानुसार Big – O Notation के रूप में लिख सकते हैं-

O( n ) * O( Complexity of Inner Loop )

Inner Loop में भी केवल एक ही printf() Statement है इसलिए Inner Loop के लिए भी ये माना जा सकता है कि Inner Loop के सभी Iteration की Complexity समान है। यानी

Complexity of Inner Loop     =    O( n ) * O( printf )

printf() Statement केवल एक ही बार लिखा गया है इसलिए स्वयंं printf() Statement की Complexity O(1) है। सभी मानों को एक साथ लिखने पर हमें इस Program की Complexity निम्नानुसार प्राप्त होती है-

[code]
//========================================
f( n ) = O( n ) * O( n ) * O( 1 )
       = O( n * n )
       = O( n2)
//========================================
[/code]