Analyzing Algorithms – Finding Complexity

Analyzing Algorithms – Finding Complexity – पिछले Post में हमने एक Program की Complexity यानी Program की Efficiency को Check किया था।

चलिए, एक और Sample Program की Complexity ज्ञात करते हैं। Program निम्नानुसार है-

[code]
Example 
//======================================================
main()
{
unsigned int i, j, n;
printf("Enter a Nonzero Positive Value as a limit : ");
scanf("%d", &n);
for( ; n>1; )
{
      n = n/2;
      printf("%d\n", n);
}

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

इस Loop की Complexity ज्ञात करने के लिए भी हम वही Formula Use कर सकते हैं जिसे पिछले Program के लिए Use किया है। इस Loop के हर Iteration की Complexity समान है इसलिए इसे हम O(1) के रूप में लिख सकते हैं। Loop कितनी बार Iterate होगा इसे ज्ञात करने के लिए हमें ये ज्ञात करना होगा कि हम किसी Number n को कितनी बार दो भागों में बांट सकते हैं जबकि n का मान 1 से बडा रहे। मानलो कि n के हर मान को K बार दो भागों में विभाजित किया जा सकता है तो इसे हम निम्नानुसार लिख सकते हैं-

2^K <= n

ये तो निश्चित है कि जब हम 2^K में 2 का भाग देते हैं तो K-1 बार 2^K का मान 2 होता है और जब हम इसे एक बार और 2 से विभाजित करते हैं तो 2^K का मान 1 हो जाता है। 2^K का मान 1 होते ही Loop Terminate हो जाता है। इसलिए जब n का मान 2^K के बराबर हो ( n = 2^K ) तब Loop K बार Repeat होगा।

चूंकि n = 2^K  है इसलिए ये Loop n के विभिन्न मानों के लिए कई बार Repeat होगा लेकिन ये Loop K + 1 Times Repeat नहीं हो सकता क्योंकि K का मान K + 1 के मान से कम होता है। इसलिए यदि n, K व घात K+1 से Bounded है तो ये Loop K बार चलता है। K व n के बीच में ये सम्बंध है कि K उस log का Integer Part है जिसका आधार 2 है। इसलिए इस उदाहरण की Complexity निम्नानुसार होगी&

O( log n ) * O( 1 ) =          O( log n )

यदि हम log के आधार 2 के स्थान पर आधार 10 को Use करें तो भी Complexity पर किसी प्रकार का कोई असर नहीं पडता है।

[code]
Example 
//======================================================
main()
{
unsigned int i, j, n;
printf(“Enter a Nonzero Positive Value as a limit : ”);
scanf(“%d”, &n);

for( i=1, m=n+66; i<=m; i++ )
{
      printf(“%d\n”, i );
}

for( j=n/21, m=n/5; j<=m; j++ )
{
      printf(“%d\n”, j );
}

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

यहां दो Independent Loops में दो printf() Statements हैं। इसलिए इस Program की कुल Complexity दोनों printf() Statements की कुल Complexity के योग के बराबर होगी। यदि इस Program को p से प्रदर्शित किया जाए तो इस Program की Efficiency को हम निम्नानुसार Big – O Notation के रूप में प्रदर्शित कर सकते हैं-

[code]
Efficiency(p) = O( Outer Loop ) + O( Inner Loop )
Outer Loop की Efficiency =  O(n)
Inner Loop की Efficiency =  O(n)
Total Efficiency         =  O(n) + O(n) 
                         =  O(n)
[/code]

चलिए, एक और उदाहरण देखते हैं। ये उदाहरण सबसे पहले उदाहरण के समान ही है लेकिन इसमें Loop के Iteration Complexity में अन्तर है। Program निम्नानुसार है-

[code]
Example 
//====================================================
main()
{
int i, j, n;
printf(“Enter the limit of Pattern”);
scanf(“%d”, &n);

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

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

इसकी Efficiency हम निम्नानुसार ज्ञात कर सकते हैं-

[code]
Efficiency(Outer Loop) 
= SUM( i, 1, n ) of (Efficiency of Ith Iteration)
= SUM( i, 1, n ) of ( n-i )
= n * ( n-1 ) / 2
= O( n * n )
= O( n2 )
[/code]