You are currently viewing Complexity Analysis

Complexity Analysis

আবুল এবং কাবুল ২ বন্ধু কম্পিউটার সায়েন্স এর স্টুডেন্ট। তো একদিন হলো কি তাদের শিক্ষক মিস্টার বাবুল সাহেব তাদের দুই জন কে ডেকে বলল যে তাদের দুই জনকে পৃথক পৃথক ভাবে একটি প্রোগ্রাম লিখে আনতে হবে যেটি কিনা কোন সংখ্যার বর্গ বের করে দিবে।

তো তারা বাড়িতে গিয়ে নিজেদের চুল ছিড়ে ,অনেক কষ্টের ফলে,অনেক মাথা ঘামিয়ে দুইজন দুই রকমের প্রোগ্রাম লিখে ফেলল। আবুলের প্রোগ্রামের অ্যালগরিদমটা ছিল এমন-for i=1 to n do n = n+n//যখন লুপ থেকে বের হবে তখন সেই ইনপুট দেয়া সংখ্যাটির বর্গ পাওয়া যাবে।return n;

এদিকে কাবুল একটু চালাক টাইপের ছেলে । সে করল কি প্রোগ্রাম টা একটু অন্যভাবে লিখে ফেলল। তার প্রোগ্রাম এর অ্যালগরিদম ছিল এরকম-/*ইনপুট হিসেবে নেয়া সংখ্যাটাকে দুই বার গুন করলেই তো বর্গ পাওয়া যাবে। তাই সে শুধু সংখ্যা দুই টাকে গুন করে যা পাওয়া যাবে তাকেই return করল।*\return n*n;

আচ্ছা এখন প্রশ্ন হলো আমরা কেন একটা কাজ কম্পিউটারকে দিয়ে করাই? উত্তরটা খুব সহজ। কম্পিউটার মানুষের থেকে খুব তাড়াতাড়ি সেই কাজটা করতে পারে। আমদের যদি এক লক্ষ সংখ্যা যোগ করতে দেয়া হয়, তাহলে আমাদের হয়তো কয়েকদিন লেগে যেতে পারে কিন্তু কম্পিটার সেটা কয়েক সেকেন্ডের মধ্যেই করে দিতে পারে। সুতরাং আমাদের কাছে সবচেয়ে গুরুত্বপূর্ন ফ্যাক্টরটা হলো “সময়”। আবার এ ক্ষেত্রে আর একটি ফ্যাক্টর গুরুত্বপুর্ন ভূমিকা পালন করে । সেটি হলো মেমোরি বা স্পেস। সুতরাং একজন প্রোগ্রামারের স্বার্থকতা হলো সে কত দ্রুততার সাথে সবচেয়ে কম মেমোরি অপচয় করে প্রোগ্রামটি রান করতে পারে। আর এখানেই চলে আসে টাইম এবং স্পেস কমপ্লেক্সিটির কনসেপ্টটি ।

তো টাইম ও স্পেস কমপ্লেক্সিটি পরিমাপ করার জন্য বিভিন্ন গাণিতিক ফাংশন আছে । তবে আমরা সব ধরনের জটিলতা উপেক্ষা করে এখানে শুধু মাত্র বিগ-ও (O) ফাংশন নিয়েই আলোচনা করব।

আচ্ছা এখন আমরা ছোট্ট একটা অ্যালগরিদম লিখে টাইম কমপ্লেক্সিটির বিষয়টি বুঝতে চেষ্টা করি।//দুইটা সংখ্যা যোগ করার জন্য অ্যালগরিদম int n1, n2, resultn1 = 100n2 = 200result = n1+n2return result;এই প্রোগ্রামটিতে আমরা কয়েকটি কাজ করেছি-১. n1 ভেরিয়েবল এর মধ্যে 100 রাখা।২. n2 ভেরিয়েবল এর মধ্যে 200 রাখা ।৩. n1 এবং n2 যোগ করা ।৪. যোগফলটি result নামক ভেরিয়েবল এর মধ্যে রাখা।

এখানে কম্পিউটার যেটা করে সেটা হলো n1 এবং n2 এর যেকোনো মানের জন্যই কম্পিউটার কাজটি একবারে করে ফেলে । এরকম পরিস্থিতিতে কমপ্লেক্সিটির হিসাবে আমরা জিনিসটাকে O(1) বলতে পারি ।অর্থাৎ যেসকল হিসাব-নিকাশ কম্পিউটার একবারে করে ফেলতে পারে কিংবা অন্যভাবে বলতে গেলে যেসকল কাজের ক্ষেত্রে কম্পিউটারের অপারেশন সংখ্যা কনস্ট্যান্ট হয় সেসকল ক্ষেত্রে কমপ্লেক্সিটির মান সবসময় O(1) হয়। তাহলে উপরের প্রোগ্রামে আমরা মোট চারটি কাজ করেছি এবং দেখা যাচ্ছে যে এক্ষেত্রে চারটি কাজ-ই কনস্ট্যান্ট অপারেশনে সম্পন্ন হচ্ছে । তাহলে আমাদের পুরো প্রোগ্রামটি চলতেও একটা কনস্ট্যান্ট সময় লাগবে। আর এজন্য আমাদের এই প্রোগ্রামের কমপ্লেক্সিটি হচ্ছে O(1)।

এখন আমরা আমাদের প্রথম উদাহরণ আবুল এবং কাবুলের কাছে ফিরে গিয়ে দেখব যে কার প্রোগ্রামটি বেশি ইফিশিয়েন্ট ।

আবুলের প্রোগ্রামটিতে আমরা দেখেছিলাম যে তার প্রোগামটি 1 থেকে শুরু করে n পর্যন্ত চলবে। তাহলে এখানে লুপের মধ্যে মোট অপারেশন সংখ্যা কিন্তু n এর মানের উপর নির্ভর করছে । n এর মান যদি 1 হয় তাহলে মোট অপারেশন সংখ্যা 1, n এর মান 2 হলে অপারেশন সংখ্যা 2 । অনুরুপভাবে n এর মান 100 হলে মোট অপারেশন সংখ্যা 100 । তাহলে এক্ষেত্রে লুপের মধ্যে কমপ্লেক্সিটি হচ্ছে O(n) ।

আবার লুপ থেকে বের হওয়ার পর আবার সব অপারেশন গুলো একটা কনস্ট্যান্ট টাইমে সম্পন্ন হবে । সুতরাং এক্ষত্রে মোট কমপ্লেক্সিটি হবে O(n)+O(1) । এখন O(n) এর তুলনায় O(1) এর মান খুব ক্ষুদ্র। তাই এক্ষেত্রে টাইম কমপ্লেক্সিটির মান হবে O(n) ।এবার আমরা কাবুলের প্রোগ্রামটি দেখব। কাবুলের প্রোগ্রামটিতে আমরা দেখতে পাই যে n এর মান যাই হোক না কেন, আমরা শুধু মাত্র n কে দুইবার গুন করে যা পাচ্ছি তাই রিটার্ণ করছি । তাহলে এক্ষেত্রেও অপারেশন সংখ্যা কনস্ট্যান্ট । আর এজন্য কাবুলের প্রোগ্রামের কমপ্লেক্সিটি O(1) ।

তাহলে আমরা বলতে পারি যে কাবুলের প্রোগ্রামটি নির্দিষ্ট কিছু কনস্ট্যান্ট অপারেশনে সম্পন্ন হয়। তাই কাবুলের প্রোগ্রামের কমপ্লেক্সিটি আবুলের কমপ্লেক্সিটির তুলনায় কম হওয়ার কারনে কাবুলের প্রোগ্রামটি অনেক বেশি ইফিসিয়েন্ট।

এবার আমরা কিছু উদাহরণ দেখব এবং সেগুলোর কমপ্লেক্সিটি হিসেব করতে চেষ্টা করব ।int sumfor i =1 to n{for j = i to n{sum+=(i+j);}}return sum;}

এই অ্যালগরিদমে প্রথমের লুপটা চলেছে n বার । পরেরবার চলেছে n-1 বার ।তাহলে মোট লুপ চলেছে = n+(n-1)+(n-3)+……+1 = (n*(n+1))/2 = (n^2+1)/2 বার ।

এখানে n^2 এবং n^2+n এর মধ্যে খুব বেশি পার্থক্য নেই । আবার n^2 এবং n^2/2 এর মধ্যেও খুব বেশি পার্থক্য নেই । সুতরাং উপরোক্ত অ্যালগরিদমের কমপ্লেক্সিট হচ্ছে O(n^2)।এবার আমরা বাইনারি সার্চের অ্যালগরিদমটি দেখে তার কমপ্লেক্সিটি হিসেব করব।low=1,high=n;while(low<=high){int mid=(low+high)/2if(key<val[mid]) low=mid-1if(key>val[mid]) high=mid+1if(key==val[mid]) return 1}এখানে আমরা প্রতিবার n এর মানকে 2 দ্বারা ভাগ করে দিচ্ছি । এখন প্রশ্ন হলো একটি সংখ্যাকে 2 দ্বারা কতবার ভাগ করা যায় ? সহজ হিসাব log2n বার।

তাহলে আমরা বলতে পারি যে লুপটি log2n বার পর ব্রেক করবে । তাহলে এই প্রোগ্রামটির কমপ্লেক্সিটি হবে O(log2n)।তাহলে আমরা এতোক্ষন পর্যন্ত যা দেখলাম তাহলো কমপ্লেক্সিটি হিসাব করার সময় কনস্ট্যান্ট অপারেশন গুলোকে বাদ দিতে হয় । এবার আমরা কয়েকটা ফাংশন দেখে তাদের কমপ্লেক্সিটি বলে দিব ।যদি কোনো একটি অ্যালগরিদম এর মোট ইনস্ট্রাকশন সংখ্যা এমন হয় যে –O(n^5)+O(n^4)+O(n^3)+O(n^2)+O(n)+O(nlogn)+O(1) তাহলে তার কমপ্লেক্সিটি হবে O(n^5) কারন O(n^5) এর তুলনায় বাকি টার্ম গুলো অনেক ছোট। এবার স্পেস কমপ্লেক্সিটি নিয়ে কিছু কথা বলা যাক । ধরা যাক, একটি প্রোগ্রাম লিখতে বলা হলো যেটি কিনা কোনো সংখ্যা জোড় বা বিজোড় সেটি বের করতে হবে । তাহলে আমরা কোনো একটা ভেরিয়েবল এর মাধ্যমে একটা সংখ্যা ইনপুট নিব। তাহলে এক্ষেত্রে স্পেস কমপ্লেক্সিটির মান হবে O(1) কারন ইনপুট এর মান যতো বড়োই হোক না কেন আমরা শুধু একটা ভেরিয়েবল এর মাধ্যমেই ইনপুট নেয়ার কাজটি করেছি ।এবার আমরা যদি a[n] সাইজের একটি অ্যারে ডিক্লেয়ার করি তাহলে সেক্ষত্রে স্পেস কমপ্লেক্সিটি কত হবে ? হিসেব টা কঠিন কিছু না। কারন এখানে কতগুলো ভেরিয়েবল থাকবে সেটা n এর মান এর উপর নির্ভর করছে । তাহলে এক্ষত্রে স্পেস কমপ্লেক্সিটি হচ্ছে O(n) ।

আজ এ পর্যন্তই…

Leave a Reply