টাইম কমপ্লেক্সিটি

অ্যালগোরিদমের কার্যকারিতা

চৌকস অ্যালগোরিদম ডিজাইন করা আমাদের উদ্দেশ্য। অর্থাৎ আমাদের জানতে হবে ডিজাইন করা অ্যালগরিদমটি কতটুকু কার্যকরী। অ্যালগোরিদমের কার্যকারিতা নিরূপণে আমরা প্রধানত দুইটি বিষয় বিবেচনায় আনতে পারি –

·         সময়ঃ অ্যালগরিদমটি যে সমস্যা সমাধানের জন্য ডিজাইন করা হয়েছে তা সমাধান করতে কতটুকু সময় নিচ্ছে।এটাকে টাইম কমপ্লেক্সিটি বলে।

·         মেমরিঃ অ্যালগরিদমটি সমস্যা সমাধানের সময় কতখানি কম্পিউটার মেমরি ব্যাবহার করছে। এটা স্পেস কমপ্লেক্সিটি নামে পরিচিত।  

টাইম কমপ্লেক্সিটি

একটা অ্যালগোরিদম আসলেই কতটুকু সময় নেয় অর্থাৎ অ্যালগোরিদমের রানিং টাইম কত হবে সেটা কিছু বিষয়ের উপর নিরভর করে। যেমন-

·         যে কম্পিউটারে অ্যালগোরিদম টা রান করানো হচ্ছে সেটা কি সিঙ্গেল নাকি মাল্টিপ্রসেসর বিশিষ্ট?

·         কম্পিউটার আর্কিটেকচার – ৩২ বিট নাকি ৬৪ বিট ?

·         ইনপুট

তবে টাইম কমপ্লেক্সিটি নির্ণয়ের সময় কম্পিউটার কনফিগারেশন কে বিবেচনায় আনা হয় না।বিভিন্ন মানের বা সাইজের ইনপুটের জন্য প্রাপ্ত সময়ের সাপেক্ষে গ্রোথ রেট হিসেব করা হয়।এখন চিন্তার বিষয় হচ্ছে কিভাবে আমরা গ্রোথ রেটের জন্য রাশি প্রতিপাদন করতে পারি।তো সেজন্য একটা মডেল কম্পিউটার বিবেচনায় আনা যাক যা নিম্নোক্ত বৈশিষ্ট্য বহন করেঃ

• -          সিঙ্গেল প্রসেসর বিশিষ্ট
• -          ৩২ বিট আর্কিটেকচার
• -          আর ধরে নিলাম যোগ-বিয়োগ এবং লজিকাল অপারেশান, ভ্যারিয়েবল আসাইন এবং ভ্যালু রিটার্ন করতে আমাদের মডেল কম্পিউটারের ১ ইউনিট সময় লাগে।

-          মডেল কম্পিউটার টি নির্দেশনাসমূহ একটার পর একটা সম্পাদন করে।

তাহলে এখন একটা সহজ উদাহরণ দেখা যাক।২ টা সংখ্যা যোগ করার অ্যালগোরিদম ডিজাইন করব আমরাঃ

Summation (NUM1, NUM2)

{

            return NUM1 + NUM2 ;

}

এবার উপরের অ্যালগরিদমটি আমদের মডেল কম্পিউটারে রান করাব।এখানে দেখা যাচ্ছে ১ টা যোগ অপারেশান করা হয়েছে এবং যোগফলটি রিটার্ন করা হয়েছে।তাহলে এই অ্যালগোরিদমের রানিং টাইম হবে,

T_summation = 1 unit time for addition + 1 unit time for returning

               = 2 unit time

তাহলে আমরা বলতে পারি এটা একটা constant টাইম অ্যালগোরিদম।

আরও একটা উদাহরণ দেখা যাক। 1 + 2 + 3 + ……… + n পর্যন্ত যোগফল বের করার অ্যালগোরিদম ও তার রানিং টাইম হিসাব করব;

Line no.	Pseudocode	Cost	No. of time
1.     2.    3.    4.	Determine_SUM(n) {    sum: = 0;    for present_number: = 1 to n do        sum = sum + present_num;  return sum; }	1  ( C1)     2  ( C2)     2  ( C3)     1  ( C4)	1    n+1    n    1

           

উপরের টেবিলে 1 + 2 + 3 + ……… + n পর্যন্ত যোগফল বের করার  Pseudocode 

দেখানো হয়েছে। ১ নং লাইনে ‘sum’ variable এ ‘০’ অ্যাসাইন করতে কস্ট হয়েছে ১ এবং No. of operation = 1 । ২ নং লাইনে(for i = 1; i<= n; i++) আমরা দুইটা কাজ করেছি – একটা কম্পারিজন আর অন্যটা increment. তাই ২ নং লাইনের কস্ট ২ এবং No. of operation = n + 1 (1 থেকে n পর্যন্ত n বার ও false condition এর জন্য 1 বার ; এই মোট n + 1 বার) । ৩ নং লাইনে ২ টা কাজ করা হয়েছে – একটা যোগ আর একটা অ্যাসাইন। তাহলে ৩ নং লাইনের মোট কস্ট ২ এবং No. of operation = n । ৪ নং লাইনে রিটার্ন করা হয়েছে সুতরাং কস্ট ১ এবং No. of operation = 1  . তাহলে অ্যালগরিদমটির মোট রানিং টাইম হচ্ছে –

T_sum = 1 + 2(n+ 1) + 2n + 1 = 4n + 4

অথবা, T (n) = Cn + C’ where C = C₂ + C₃ C’ = C₁ + C₂ + C₄

এবার দুইটা ম্যাট্রিক্স এর যোগফল বের করার অ্যালগোরিদম ডিজাইন করা যাক ।

A = [ 2 3]                     B = [6   7]                     C = A + B = ?

       [4  5]                            [8 9]

Pseudocode:

Sum_Matrix( A , B )

{

for i: =1 to n do

    for j: =1 to n do

         C [i] [j] = A [i] [j] + B [i] [j];

Print ß C

}

• উপরের কোডে ভেতরের লুপ টা n বার ঘুরবে। পরেরবার ঘুরবে n-1 বার। তাহলে মোট লুপ চলেছে n + (n-1) + (n + 2) + …….. + 1 = n(n+ 1) / 2  বার।অর্থাৎ T_matrixSum = n²/2 + n/2 যা an²+ bn + c এর মত । তাহলে প্রথম উদাহরনের constant time complexity , ২য় উদাহরনের লিনিয়ার টাইম কমপ্লেক্সিটি, ৩য় উদাহরনের quadratic টাইম কমপ্লেক্সিটি। সুতরাং এদেরকে গ্রাফে স্থাপন করলে নিচের চিত্র পাওয়া যাবেঃ
  

অ্যালগোরিদমের হাতেখড়ি

অ্যালগোরিদম কি?

আমরা যে কাজই করি না কেন, কিছু নির্দিষ্ট ধাপ অবলম্বন করে করি।আর এই ধাপগুলোর সমষ্টি অ্যালগোরিদম। আর কম্পিউটার অ্যালগোরিদম হল কম্পিউটার যে সুনির্দিষ্ট উপায়ে কোন সুনির্দিষ্ট কাজ করে।

কিন্তু কথা হচ্ছে কম্পিউটার কি আসলেই নিজে থেকে কিছু করতে পারে। উত্তর হচ্ছে পারে না। আমারাই কম্পিউটার কে শিখিয়ে দিই কোন উপায়ে কাজটি করতে হবে।তাহলে বোঝা যাচ্ছে আমরা যত ভালোভাবে কম্পিউটার কে নির্দেশনা দিতে পারব তত নির্ভুল ও দক্ষভাবে আমাদের কাজটি সে করে দিবে। তো আমরা যে অ্যালগোরিদম ডিজাইন করব অবশ্যই তার কিছু বৈশিষ্ট্য থাকতে হবে। যেমন-

·         আপনাকে অবশ্যই কিছু না কিছু ইনপুট দিতে হবে। ইনপুট দিবেন না , আউটপুট আশা করবেন , তা হবে না তা হবে না।

·         আপনি ইনপুট দিয়ে আউট পুট পেলেন না , তাইলে অমন অ্যালগোরিদম ডিজাইন করার কি দরকার বলেন ? অর্থাৎ আপনার অ্যালগোরিদমের অবশ্যই আউট পুট দেবার ক্ষমতা থাকতে হবে।

·         আপনার নির্দেশনা স্পষ্ট হতে হবে তার মানে হল কি করতে হবে সেটা একদম ক্লিয়ার- কাট হতে হবে।

·         আর হ্যাঁ আপনার অ্যালগোরিদম কে কিন্তু সময়ের দিকে খেয়াল রাখতে হবে। এমন অ্যালগোরিদম ডিজাইন করলেন যার আউট পুট পেতে পেতে হাই উঠে যায়, সকাল গড়িয়ে সন্ধ্যা হয়ে যায় তাইলে তো চলবে না , তাই না বলেন? অলস অ্যালগোরিদম চলবে না, চৌকশ অ্যালগোরিদম ডিজাইন করুন।

অ্যালগোরিদম কেন দরকার?

আপনি কোন কিছু জানার দরকার পড়লে কি করেন?অনেক ধরনের উত্তর আসতে পারে।সহজতম উত্তর হল ইন্টারনেট সার্চ। মুহূর্তের মধ্যে এত এত তথ্যের মধ্যে থেকে আপনার প্রয়োজনীয় টা সার্চ ইঞ্জিন গুলো কিভাবে আপনার সামনে তুলে ধরে।অত্যন্ত চৌকস অ্যালগোরিদম এর কারনেই এটা সম্ভব।

আবার ধরুন আপনাকে বাংলাদেশ সরকার আদমশুমারির দায়িত্ব দিল।তারপর আপনাকে বলল ছোট থেকে বড় বয়স অনুযায়ী সাজাতে।এদের মধ্যে কতজন ২০ থেকে ২৫ বছরের মধ্যে?সেই ২০-২৫ বছরের বয়সীদের মধ্যে কতজনের নাম মেহমাত? ভাবুন তো এত বিশাল কাজ কি আদৌ নির্দিষ্ট সময়ে করা সম্ভব।

এভাবে ভাবতে থাকুন নিজেই খুজে পাবেন অ্যালগোরিদম জানার ও শেখার প্রয়োজন কেন ও কতটা?

অ্যালগোরিদম কিভাবে বর্ণনা করব?

অ্যালগোরিদম সাধারন ভাষা(বাংলা, ইংরেজি) দিয়ে বর্ণনা করা যায় অথবা ফ্লো-চার্ট দিয়েও প্রকাশ করা যায় অথবা সুডোকোড ব্যাবহার করা যেতে পারে।

আচ্ছা ধরুন আমরা 1 + 2 + 3 + ………. + n পর্যন্ত যোগফল নির্ণয়ের জন্য অ্যালগোরিদম ডিজাইন করব।নিম্নে তিন উপায়ে দেখানো হল কিভাবে এই অ্যালগোরিদম টা প্রকাশ করা যায়ঃ

1.      Using English Language:

Step - i. Summation ß 0

Step - ii. Present number ß 1

Step – iii. Is present number <= n?

Step – iv. If answer is ‘yes’ of the question of step – iii, then Summation ß Summation + present number

Step – v. present number ß present number + 1

Step – vi. Go to step – iii

Step – vii. If answer is ‘no’ of the question of step – iii, then prints the summation

2.      Using pseudocode:

Determine_SUM(n)

{

sum: = 0;

            for present_number: = 1 to n do

            {

                        sum = sum + present_num;

            }

            return sum;

}

                       

3.      Using flowchart:

Description of Algorithm