WordPress Bangla Tutorial

Time & Space Complexity কী? Data Structure Complexity Bangladesh

ডেটা স্ট্রাকচার ও অ্যালগোরিদম জানার পূর্বে জানা উচিত Time & Space Complexity কী?

ডেটা স্ট্রাকচার ও অ্যালগোরিদম শেখার পূর্বে যে বিষয়টি প্রথম চলে আসে সেটা হলো টাইম এবং স্পেস Complexity । Time & Space Complexity নিয়ে কথা বললে অনেক কথাই বলা যায়। 
বেশি গভীরে গিয়ে বুঝতে চেষ্টা করলে এ বিষয়ে বেশ খাটনি করে জেনে নিতে হবে। আমি ছোট করে তোমাদের কে বোঝানোর চেষ্টা করছি।

Time complexity : টাইম কমপ্লেক্সজিটি বলতে বুঝায় একটি কাজ করতে একটি প্রোগ্রামের ঠিক কতটুকু সময় লাগবে, এই সময় সম্পর্কে জানতেই টাইম কমপ্লেক্সজিটির কথাটি চলে আসে। আমরা একই প্রোগ্রামকে যেমন বিভিন্নভাবে লিখতে পারি তেমনি, একটি প্রোগ্রামের ও রয়েছে বিভিন্ন রকমের অ্যালগোরিদম।কোন অ্যালগোরিদমটি তোমার প্রোগ্রামের জন্য বেশি ইফেক্টিভ হবে তুমি এই দুইটি বিষয় দিয়ে সেটা নির্ধারণ করতে পারবে।এই বিষয়ে এখন তোমাকে বেশি কিছু না জানলেও চলবে। তুমি শুধু মনে রাখ এইটুকুই যে, একটা প্রোগ্রাম ইনপুট গ্রহণ করে আউটপুট পর্যন্ত মাঝখানে যে সময়টুকুন লাগে সেটাই টাইম কমপ্লেক্সজিটি।

Space Complexity : টাইম কমপ্লেক্সজিটির সাথে আরো একটি বিষয় চলে আসে সেটা হলো Space Complexity ।
Space Complexity মানে হল একটি প্রোগ্রাম কম্পিউটার মেমরীতে ঠিক কতটুকুন জায়গা নিবে, সেটাকে বোঝায়।
একটি প্রোগ্রাম লিখলেই শুধু হবে না। প্রোগ্রাম লেখার সময় অবশ্যই তোমাকে খেয়াল করে লিখতে হবে যেন, প্রোগ্রামটি লোড হতে টাইম কম লাগে এবং সেই প্রোগ্রামটির জন্য কম্পিউটার মেমরিতে জায়গাও কম লাগে। মূলত এই দুইটি বিষয়ের জন্যই টাইম এবং স্পেস কমপ্লিক্সজিটির ব্যবহার চলে আসে। এই দুইটি বিষয় মাথায় রেখে কোড করলে তোমার প্রোগ্রাম অনেক বেশি Faster হবে। টাইম এবং স্পেস কমপ্লিক্সজিটি প্রকাশের জন্য বিভিন্ন গাণিতিক ফাংশন রয়েছে, যেমন ঃ থেটা, ওমেগা, বিগ-ও। এই গাণিতিক ফাংশনগুলো জানার জন্য তোমাকে ডিসক্রিট ম্যাথমেটিকস সম্পর্কে জ্ঞান লাভ করতে হবে।

এখন আমরা গাণিতিক ফাংশনগুলোর মধ্যে থেকে বিগ-ও সম্পর্কে জানবো।অন্যসব ফাংশন এখন না জানলে ও চলবে।এখন আমি কিছু উদাহরণের সাহায্য বিগ-ও কি তা বোঝাতে চেষ্টা করছি।
আমরা দুইটি সংখ্যার যোগের প্রোগ্রাম দেখবো।

let num1 = 50;
let num2 = 30;
let result = num1 + num2;
প্রথম ভেরিয়াবলে আমরা 50 এসাইন করেছি, দ্বিতীয়টিতে ৩০ এসাইন এবং রেসাল্ট এ একটি যোগ ও একটি এসাইনমেন্ট অপারেশন করেছি। এখানে মোট চারটি অপারেশন হয়েছে যেমন তিনটি এসাইনমেন্ট অপারেশন এবং একটি যোগ অপারেশন।এটার কমপ্লেক্সজিটি হবে O(1)।  এটাকে আমরা পড়তে পারি বিগ-ও ওয়ান বা O(1)। মানে হলো অর্ডার অফ ওয়ান। এখানে যদি বিশটা অপারেশন ও হতো তাহলেও আমরা O(1) ই পড়তাম।

এখন আমরা আরেকটি প্রোগ্রাম দেখবো। ১ থেকে n তম পদের পূর্নসংখ্যার যোগফল।
function nTomo(){
    let i,n;
    let result = 0;
    n = parseInt(prompt(‘Enter any number’));
    for(i=1;i<=n;i++){         result += i;     }     return result; } document.write(nTomo(result)); এখানে রেজাল্ট নামের ভেরিয়াবলের মধ্যে 0 এসাইন করা হয়েছে। তারপর ইউজার এর কাছ থেকে n এর সংখ্যা নিতে একটা এসাইনমেন্ট ব্যবহার করা হয়েছে। ফর লুপের মাঝে n এর মান অনুযায়ী অর্থ্যাৎ n এর মান যত হবে ফর লুপের মাঝে রেজাল্ট ভেরিয়াবল ততোবার যোগ হবে। তাইলে এটাকে আমরা পড়তে পারি o(n)। n এর মান ১০ হলে o(10) এভাবে বললে ও ভূল হবে না। কিন্তু আমরা তো জানিনা ইউজার ইনপুট কতো দিবে তাই এটাকে O(n) পড়াই ভালো। কিছু কি এখনো বুঝতে পেরেছেন? কম কম ই বুঝেছেন তাই না? এখন কার উদাহরণ দেখলে বুঝে যাবেন কেন এই কমপ্লেক্সজিটির বিষয়টি জানা গুরুত্বপূর্ণ। তাহলে ঐ n তম পদের কমপ্লেক্সজিটি কি আমরা চাইলে কমাতে পারতাম নাহ। যদি আমরা n তম পদের কমপ্লক্সজিটির মান কমাতে পারতাম তবে, আমাদের প্রোগ্রাম অধিক পরিমান ইফেশিয়েন্ট হতো। এখন দেখা যাক কিভাবে আমরা n তম পদের কমপ্লেক্সজিটি কমাতে পারি। প্রোগ্রামটি যদি আমরা এভাবে লিখতাম তাহলে কি হতো দেখুন। function nTomo(){     let n;     let result;     n = parseInt(prompt('Enter any number'));     result = n * (n+1) /2;     return result; } document.write(nTomo(result)); এখানে কি কি অপারেশন হয়েছে দেখুন। n ইনপুটে একটা এসাইনমেন্ট অপারেশন হয়েছে তারপর রেজাল্ট এ একটি এসাইনমেন্ট একটি গুণ, একটি যোগ, আর একটি ভাগ অপারেশন করা হয়েছে। এখানে কিন্তু n তম পদে মোট চারটি অপারেশন সম্পন্ন হয়েছে। এখানে n এর মান যাই হোক না কেন আমরা কিন্তু এই চারটি অপারেশন-ই করবো। তাই,আমরা  এর কমপ্লেক্সজিটি পড়বো O(1)। এই প্রোগ্রামটি দেখুনঃ let n = parseInt(prompt('Enter any number')) let i,j, count= 0; for(i=0;i

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button
error: Content is protected !!
Close
Close

Adblock Detected

Please consider supporting us by disabling your ad blocker