অ্যালগরিদমে টাইম কমপ্লিক্সিটি(complexity) - পর্ব (০১)

 

অ্যালগরিদম বা প্রোগ্রামে টাইম কমপ্লিক্সিটি(complexity) অনেক গুরুত্বপূর্ণ বিষয় । সোজা-সাপ্টায় কোনো অ্যালগরিদম বা প্রোগ্রাম রান হতে কতটুকু সময় লাগলো তাকেই টাইম কমপ্লিক্সিটি(complexity) বলে। কোনো একটা প্রোগ্রাম রান হতে ঠিক কতটুকু সময় নিলো তা আমরা বিভিন্ন লাইব্রেরী ফাংশনের সাহায্যে বের করতে পারি । কিন্তু যদি আমরা একবার এর হিসেব-নিকেশ বুঝি তাহলে যেকোনো প্রোগ্রাম রান না করেই অর্থাৎ দেখলেই বলে দিতে পারবো যে সেই প্রোগ্রাম রান হতে কেমন সময় লাগতে পারে ।

আপনি যদি বিগ ও নোটেশন (Big O) নোটেশন সম্পর্কে নাহ যেনে থাকেন তাহলে এখানে পড়ুন ।

আমরা জানি যে, কোনো একটা সমস্যা অনেক ভাবেই সমাধান করা যায় । তাই আমাদের কোনো একটা সমস্যা সমাধান করার সময় অবশ্যই মাথায় রাখতে হবে কোনটার টাইম কমপ্লিক্সিটি(complexity) কেমন এবং কোনটা বেশি  স্মার্ট ।

এই জন্যই আমাদের টাইম কমপ্লিক্সিটি(complexity) বিষয়টা ভালো করে বুঝতে হবে ।

const ghurLoop = (n) => {
    for(let i = 0; i<n; i++){
    console.log("I am haba!")
    }
}
ghurLoop(10);

আচ্ছা উপরের প্রোগ্রামে I am haba! কতো বার প্রিন্ট হবে? যার প্রোগ্রামিং সম্পর্কে বেসিক নলেজ আছে সে খুব সহজেই বলে দিতে পারবে যে ১০ বার । কারণ, আমাদের লুপটি কিন্তু ১০ বার ঘুরবে কন্ডিশন অনুযায়ী যা আমরা প্যাঁরামিটার হিসেবে পাস করেছি ।

এখন আমরা যদি ফাংশনের প্যাঁরামিটার হিসেবে ১০ না দিয়ে ২০ দেয় তাহলে I am haba! কতো বার প্রিন্ট হবে? ২০ বার তাই তো । এইভাবে যদি ১০০ বা ২০০ বা ৫০০ প্যাঁরামিটার হিসেবে পাঠায় তাহলে I am haba! ১০০ বা ২০০ বা ৫০০ বার প্রিন্ট হবে ।

এখানে কিন্তু প্যাঁরামিটার এর ওপর নির্ভর করে আমাদের লুপটি ঘুরবে । এখন আমরা বুঝতে পারছি যে, I am haba! n বার প্রিন্ট করবে ।

তাহলে আমরা খুব সহজেই বলে দিতে পারি যে, এই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) ওর্ডার অব এন O(n) ।

- Linear Time: ওর্ডার অব এন O(n) -

যখন কোনো প্রোগ্রামে কোনো কাজ একের অধিক বার কোনো ইনপুটের উপর নির্ভর করে হয় সেই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) ওর্ডার অব এন O(n) যাকে Linear Time ও বলা হয়।

যেমন -

let sum = 0;
const summetion = (n) => {
  for (let i = 0; i < n; i++) {
    sum += i;
  }
};
summetion(10);
console.log(sum);

উপরোক্ত প্রোগ্রামে -

1. sum ভ্যারিয়েবলে 0 রাখা হয়েছে ।
2. summetion(n) ফাংশন যা n নামে একটি প্যাঁরামিটার নিচ্ছে।
3. এবং ফাংশনের ভেতরে একটি লুপ আছে যা চলবে প্যাঁরামিটার এর মান পর্যন্ত ।
4. পরের লাইনে sum এর সাথে অ্যাসাইনমেন্ট ও যোগ অপারেশন হচ্ছে।

এখানে যদি n এর মান 100 পাঠানো হয় তাহলে কিন্তু অ্যাসাইনমেন্ট ও যোগ অপারেশন 100 বারই হবে সাথে sum এর মানও বাড়তে থাকবে । অর্থাৎ এখানে n এর মান যত বৃদ্ধি পাবে প্রোগ্রামে অ্যাসাইনমেন্ট, যোগ অপারেশন ও sum এর মান ততই বাড়তে থাকবে এতে প্রোগ্রামের রানটাইমও বেড়ে যাবে। এখন আমরা খুব সহজেই বলতে পারি যে, এই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) ওর্ডার অব এন O(n) ।

- Constant Time: O(1) -

যখন কোনো প্রোগ্রামে অপারেশন কন্সট্যান্ট টাইম হয় সেই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) ওর্ডার অব ওয়ান O(1)।

ছোট্ট একটি উদাহরণ -

const a = 10;
const b = 5;
const sum = a+b;
const subtract = sum - 10;

উপরের এই প্রোগ্রামে -

1. a ভ্যারিয়েবলে 10 রাখা হয়েছে । 
2. b ভ্যারিয়েবলে 5 রাখা হয়েছে । 
3. sum ভ্যারিয়েবলে (a+b) এর মান রাখা হয়েছে । 
4. subtract ভ্যারিয়েবলে (sum - 10) এর মান রাখা হয়েছে ।

এখানে a ও b ভ্যারিয়েবলের মান যতই রাখা হোক নাহ কেন আমাদের প্রোগ্রামে কিন্তু গাণিতিক অপারেশন মাত্র দুইবারই(২) হবে । অর্থাৎ a ও b ভ্যারিয়েবলের মান যদি ১০০ করে রাখি তবুও গাণিতিক অপারেশন মাত্র দুইবারই(২) হবে । তাই আমরা বলতে পারি এই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) ওর্ডার অব ওয়ান O(1)।

আমরা উপরে ফর-লুপ(for loop) ব্যাবহার করে n তম সংখ্যার যোগফল নির্ণয়ের একটা প্রোগ্রামে লিখেছি যার টাইম কমপ্লিক্সিটি(complexity) ওর্ডার অব এন O(n)।

এখন আমরা আবার n তম সংখ্যার যোগফল নির্ণয়ের একটা প্রোগ্রাম লিখবো তবে এবার কোনো লুপ(loop) ব্যাবহার করে নাহ সূত্রের সাহায্যে ।

সূত্রটি হলো - n * (n + 1) / 2 ;

 

const sum = (n) => {
  const result = n * (n + 1) / 2 ;
  console.log(result);
}
sum(4);

আচ্ছা আপনি কি বলতে পারবেন নাহ এই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) কত ? আসলে এখানে হচ্ছে টা কি -

• একটি যোগ, একটি গুণ, একটি ভাগ এবং একটি অ্যাসাইনমেন্ট এর কাজ হচ্ছে ।

তাছাড়া আর তেমন কিছু হচ্ছে নাহ । এখানে প্যাঁরামিটার ১০, ১০০, ৩০০ যেইটাই পাস করা হোক না কেন একটি যোগ, একটি গুণ, একটি ভাগ এবং একটি অ্যাসাইনমেন্ট এরই কাজ হবে এর বেশি কিন্তু হবে নাহ । তাহলে আমরা বলতে পারি এই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) ওর্ডার অব ওয়ান O(1)।

---

আরেকটি প্রোগ্রাম দেখা যাক -

const ghurLoop = (n) => {
    for(let i = 0; i<n; i = i+2){
    console.log("I am haba!")
    }
} 

এই প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) কত হতে পারে ? প্রথমে লক্ষ্য করুন যে, এইবার কিন্তু লুপে i এর মান ২ করে বাড়তেছে । তার মানে প্যাঁরামিটার যত পাঠানো হবে তার অর্ধেক বার লুপটি চলবে এবং I am haba! প্রিন্ট করবে।

যেমন আমি যদি এখন প্যাঁরামিটার ১০ পাঠায় তাহলে আউটপুট হবে -

- Pass Parameter -

ghurLoop(10)

- OUTPUT -

I am haba! I am haba! I am haba! I am haba! I am haba!

খেয়াল করছেন ? প্যাঁরামিটারের অর্ধেক বার লুপটি ঘুরলো । অর্থাৎ প্যাঁরামিটার ২০, ৫০, ২০০ যাই পাঠানো হোক না কেন তার অর্ধেক লুপটি ঘুরবে এবং I am haba! প্রিন্ট করবে ।

এখানে প্রোগ্রামের টাইম কমপ্লিক্সিটি(complexity) হলো O(n/2) ।

টাইম কমপ্লিক্সিটি(complexity) নিয়ে প্রথম পর্ব আজকে এই পর্যন্তই । আশা করি পরের পর্বগুলো আরও ইনফরমেটিভ হবে ।

# javascript time complexity

# time complexity explained

# time complexity in dsa