টাইম কমপ্লেক্সিটি O(log n) বলতে আসলে কি বুঝি?

একটা অ্যালগরিদমের টাইম কমপ্লেক্সিটি সাধারণত Big O নোটেশন দিয়ে প্রকাশ করা হয়। তো কিছু কিছু অ্যালগরিদমের টাইম কমপ্লেক্সিটি হচ্ছে O(log n)। এই O(log n) এর মানে বুঝার চেষ্টা করব এই লেখায়। সহজ কথায় যদি বলি, কোন অ্যালগরিদমের ইনপুট সংখ্যা ( n ) যদি এক্সপোনেনশিয়ালি বাড়ে, তাহলে O(log n) এর মানে হচ্ছে ঐ অ্যালগরিদম এক্সিকিউট করতে সময় বাড়বে লিনিয়ারলি। কোন অ্যালগরিদমের টাইম কমপ্লেক্সিটি যদি O(log n) হয়, তাহলে বলতেই হয় ঐটা যথেষ্ট ভালো একটা অ্যালগরিদম। যেমন O(1) > O(log n) > O(n) > O(n2) > O(n3) এভাবে যত ডান দিকে আসবে, ঐ অ্যালগরিদমের টাইম কমপ্লেক্সিটি তত বেশি। মানে তত বেশি সময় লাগবে এক্সিকিউট হতে।

সূচক ও লগারিদম

সূচকের সাথে লগারিদম সম্পর্কযুক্ত। এভাবে চিন্তা করা যায় যে সূচকের বিপরীত হচ্ছে লগ। লগের বিপরীত হচ্ছে সূচক। যেমনঃ

23 = 2 * 2 * 2 বা 23 = 8

উপরের 23 = 8 কে লগারিদমের মাধ্যমেও লেখা যায়ঃ log 2 8 = 3

এখানে 2 কে বলা হয় বেজ। 8 হচ্ছে ভ্যালু । 3 হচ্ছে এক্সপোনেন্ট।

আমরা জানি কম্পিউটার বাইনারিতে কাজ করে। তো কম্পিউটারের কোন কম্পিউটেশনের ক্ষেত্রে বেইজ হবে 2। লগ দিয়ে মূলত আমরা একটা প্রশ্নের উত্তর খুঁজি, আর তা হচ্ছে বেইজের সূচক কত হলে টার্গেট নাম্বারটা পাওয়া যাবে। উপরের উদাহরণের ক্ষেত্রে প্রশ্নটা হবে 2 এর সূচক কত হলে 8 পাওয়া যাবে। যেটাকে আমরা এভাবে লিখতে পারিঃ

2x = 8 ? যা নিচের মত করে লেখা যায়ঃ

log 28 = x ?

লগ থেকে যেহেতু সূচকে আমরা বেশি অভ্যস্ত, তাই এমন প্রশ্নের উত্তর খুঁজতে আমরা মূলত log 28 = x কে সূচক ফরমে লিখিঃ 2x = 8 যেটাকে লিখতে পারি এভাবেঃ 2³ = 8। অর্থাৎ এখানে x এর ভ্যালু হচ্ছে 3। বাঃ

log 28 = 3।

O(log n)

অনেক অ্যালগরিদম যেমন বাইনারি সার্চ অথবা অন্য কোন ডিভাইড & কনকার টাইপ অ্যালগরিদমের টাইম কমপ্লেক্সিটি সাধারণত O(log n) হয়ে থাকে। কেন O(log n) হয়, তাই এবার দেখি। আমরা জানি বাইনারি সার্চ লিস্ট কোন আইটেম খুঁজে বের করার জন্য প্রতি স্টেপে আইটেমকে দুই ভাগে ভাগ করে ফেলে। নিচের ছবিটি দেখি। এখানে ৮টা আইটেম নিয়েছি।

ইনপুট সংখ্যা ৮ হলে আমরা যদি হিসেব করি, তাহলে দেখব তিনটা স্টেপেই আমরা হয় টার্গেট ভ্যালুটি লিস্টে পাবো অথবা লিস্টে ঐ সংখ্যাটি থাকবে না। আরো সহজ উদাহরণ দেইঃ

• 8/2 = 4
• 4/2 = 2
• 2/2 = 1

এরপর তো কোন লিস্টকে ভাগ করা যায় না। এবার লগে ফিরে আসি। আমরা জেনেছি যে বাইনারি সার্চের টাইম কমপ্লেক্সিটি O(log n)। এখানে n হচ্ছে ইনপুট সংখ্যা। উপরের লিস্টে ইনপুট সংখ্যা হচ্ছে 8। আবার কম্পিউটারের ক্ষেত্রে বেইজ হচ্ছে 2। O(log n) এর মানে মূলত O(log ₂n)। যেখানে এই বেইজ উয্য থাকে।

তাহলে log ₂8 = এর মান কত হচ্ছে উপরের বাইনারি সার্চের ক্ষেত্রে? 3, তাই না? এখন বুঝতে পেরেছি কেন বাইনারি সার্চের টাইম কমপ্লেক্সিটি O(log n)?

আরেকটা উদাহরণ দেখি। এবার দেখি ইনপুট সংখ্যা যদি ১৬ হয়, তাহলে কয়টা ধাপ লাগবেঃ

এখানে আমরা ইনপুট সংখ্যা বাড়িয়ে ১৬ করেছি। এখানে দেখছি আমাদের সর্বোচ্চ ৪টা ধাপ লেগেছে টার্গেট ভ্যালুটি খুঁজে বের করতে। এর মানে হচ্ছে log ₂16 = 4। এর মানে ইনপুট সংখ্যা এক্সপোনেনশিয়ালি বাড়লেও টাইম কমপ্লেক্সিটি বাড়ছে লিনিয়ারলি।