মুশফিকুর রহমান নিলয়

অ্যালগরিদমের টাইম কমপ্লেক্সিটি পর্ব ০২

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

উপরের প্রোগামের টাইম কমপ্লেক্সিটি কত হবে? এই লুপটি কতবার ঘুরবে? এখানে লক্ষ্য করে দেখো i ভ্যালু কিন্তু ২ করে গুন হচ্ছে।
আমরা n এর মান বিভিন্ন রকম দিয়ে দেখি লুপটা কতবার ঘুরে।

n এর মান যদি 1 দেই তাহলে লুপটা ১ বার ঘুরবে। n এর মান যদি 2 দেই তাহলে লুপটি ২ বার ঘুরবে। কারণ (2 x 2 = 4) হবে সুতরাং কন্ডিশন মিথ্যা। n এর মান যদি 4 দেই তাহলে লুপটি 3 বার ঘুরবে। কারণ (4 x 2 = 8) হবে সুতরাং কন্ডিশন মিথ্যা। n এর মান যদি 8 দেই তাহলে লুপটি 4 বার ঘুরবে। কারণ (8 x 2 = 16) হবে সুতরাং কন্ডিশন মিথ্যা। n এর মান যদি 16 দেই তাহলে লুপটি 5 বার ঘুরবে। কারণ (16 x 2 = 32) হবে সুতরাং কন্ডিশন মিথ্যা। n এর মান যদি 32 দেই তাহলে লুপটি 6 বার ঘুরবে। কারণ (32 x 2 = 64) হবে সুতরাং কন্ডিশন মিথ্যা।
এখন তোমাদের জন্য আমার প্রশ্ন হলো, n এর মান যদি 22 দেই তাহলে লুপটি কতবার ঘুরবে?

n এর মান বিভিন্ন রকম দিয়ে দেখলাম লুপটা কতবার ঘুরে। এখন n এর মানটা কে যদি পাওয়ারে কর্নভার্ট করার চেষ্টা করি। যেহেতু প্রত্যেকবার ২ দিয়ে গুন হচ্ছে।

উপরের টেবিল অনুযায়ী n=8 এর জন্য 2 এর ম্যাক্সিমাম পাওয়ার হচ্ছে 4। n=16 এর জন্য 2 এর ম্যাক্সিমাম পাওয়ার হচ্ছে 5। এখন তোমাদের কাছে প্রশ্ন হলো n=22 এর জন্য 2 এর ম্যাক্সিমাম পাওয়ার কত?
তাহলে 2 এর পাওয়ার ধরে ম্যাক্সিমাম পাওয়ারটা কে বের করবো এবং তার সাথে 1 যোগ করতে হবে। যেহেতু পাওয়ার 0 থেকে শুরু হয়েছে।

আমরা কিন্তু এখন পর্যন্ত এই প্রোগ্রামের টাইম কমপ্লেক্সিটি টা বের করতে পারিনি। এতক্ষণ শুধু লুপটা কতবার ঘুরে সেটা বের করলাম।
এই প্রোগ্রামের টাইম কমপ্লেক্সিটি বের করতে হলে ম্যাথের log এর সাহায্য নিতে হবে। চিন্তার কোন কারণ নেই, এটার জন্য হাইলেভেল ম্যাথ জানা লাগবে না। স্কুলে থাকতে নবম এবং দশম শ্রেণীতে যে log এর ম্যাথ করে আসছি সেটাই যথেষ্ট। তারপরেও নিচে একটা আইডিয়া দেওয়ার চেষ্টা করা হলো।

যদি উপরের ইকুয়েশনটা বুঝে থাকো তাহলে log232 এটা কত হবে?
log232 = log226 = 6log22 = 6 * 1 = 6

তাহলে n = 32 এর টাইম কমপ্লেক্সিটি হবে O(log232 + 1)। আমরা আগেই বলেছিলাম পাওয়ার 0 থেকে শুরু হইছে।
n = 16 এর টাইম কমপ্লেক্সিটি হবে O(log216 + 1)। সুতরাং n এর টাইম কমপ্লেক্সিটি হবে O(log2n + 1)।
তোমাদের কাছে আমার প্রশ্ন হলো n = 22 এর টাইম কমপ্লেক্সিটি কত হবে?

একটু সহজ করে বললে, যদি দেখো i এর ভ্যালু গুন করে বৃদ্ধি পাচ্ছে তাহলে log এর সাহায্য নিতে হবে। সেটা হতে পারে 2 অথবা 3 অথবা 4। অর্থাৎ যে সংখ্যা দ্বারা গুন হবে সেটা হবে log এর বেইস।

এবার বলোত নিচের প্রোগ্রামটা কতবার ঘুরবে এবং এর টাইম কমপ্লেক্সিটি কত? উপরের প্রোগ্রামের ঠিক উল্টো এটা।

এখান একটু খেয়াল করে দেখো i এর ভ্যালু n এবং প্রতিবার i এর ভ্যালু 2 দিয়ে ভাগ হচ্ছে। সব কিছুই আগের মত থাকবে। i এর মান যদি 16 দেই তাহলে 16 কে 2 দিয়ে ভাগ করলে হবে 8, 8 কে 2 দিয়ে ভাগ করলে হবে 4। এভাবে i এর মান 1 হবে। কিন্তু আমাদের লুপের কন্ডিশনে বলা আছে 1 এর নিচে নামা যাবে না। সুতরাং এখানেও টাইম কমপ্লেক্সিটির কোন পরিবর্তন হবে না।
অর্থাৎ গুনের সময় উপর থেকে নিচে নামতেছিলাম আর ভাগের সময় নিচ থেকে উপড়ে উঠবো।

আজকের পর্বে এতটুকুই। আগামী পর্বে নেস্টেট লুপের টাইম কমপ্লেক্সিটি বের করা দেখবো।