টাইম কমপ্লেক্সিটি

টাইম কমপ্লেক্সিটি:

টাইম কমপ্লেক্সিটি নামটা একটু কঠিন। এইটার নাম আমি দিলে এইটার নাম হতো- "কতক্ষণ লাগবে?" বা আরেকটু গুছিয়ে বললে বলবো- "কোড রান করতে কতক্ষণ লাগবে?", বা "কোড কতবার চলবে?

যেমন ধর তোর কাছে একটা friends নামে একটা array আছে। সেটার মধ্যে তোর সব ফ্রেন্ডের নাম লেখা আছে। এখন তুই একটা for লুপ চালিয়ে তোর friends নামক array এর সব উপাদানকে আউটপুট হিসেবে দেখতে চাস, নিচের মতো


var friends = ["abul", "babul", "cabul", "dabul"];

for(var i = 0; i< friends.length; i++){
	var friend = friends[i];
	console.log(friend);
}

এই কোড রান করলে কয়টা আউটপুট দেখবি?

চারটা

কারণ তোর friends নামক array তে চারটা উপাদান আছে।

বিশ্বাস না হলে, www.habluderadda.com/consoleএ গিয়ে টাইপ করে চেক করে দেখ

যদি তোর friends নামক array তে চারটা উপাদান না থেকে পাঁচটা উপাদান থাকতো তাহলে কয়টা আউটপুট দেখতি? নিশ্চয়ই পাঁচটা দেখতি। আর তোর friends নামক array তে চৌদ্দটা উপাদান থাকলে তুই চৌদ্দটা আউটপুট দেখতি।

তারমানে তোর array এর মধ্যে যতগুলা উপাদান আছে, যতগুলা আউটপুট দেখাবে।

উপরের for লুপের দিকে আরেকবার তাকা। দেখবি লুপের ভিতরে একবার করে আউটপুট দেখানো আছে। আর লুপ একবার চললে একবার আউটপুট দেয়। তাই যদি চৌদ্দবার চলে, তাহলে চৌদ্দটা আউটপুট দেখায়।

তারমানে কতবার চলবে সেটা নির্ভর করতেছে কতটা উপাদান আছে। অর্থাৎ চারটা থাকলে চারবার। পাঁচটা থাকলে পাঁচবার। চৌদ্দটা থাকলে চৌদ্দবার। আর উপাদান সংখ্যা n হইলে, n বার চলবে।

যদি কোন একটা কোড বা n বার চলে তাকে প্রোগ্রামিংয়ের ভাষায় বলে এইটা O(n) বার চলবে। বা সেই কোডের টাইম কমপ্লেক্সিটি (time complexity) হচ্ছে O(n)

এইখানে O আছে Order শব্দ এর প্রথম অক্ষর থেকে। অর্ডার (order) শব্দের বাংলা অর্থ হচ্ছে মাত্রা। সেটা একটু পরে একটু ভালো করে বুঝা যাবে। আপাতত সামনে আগাইতে থাক।

ডাইরেক্ট একশন:

ধর তুই তোর friends নামক array থেকে যেকোন একটা উপাদান বের করতে চাস। ধরে তুই ২পজিশনে থাকা উপাদানকে বের করতে চাস। তাহলে তুই নিচের মতো করে কোড লিখবি।


var friends = ["abul", "babul", "cabul", "dabul", "ebul"];
var friend = friends[2];

এই যে একটা নিদৃষ্ট পজিশন থেকে একটা উপাদান বের করছস। সেটা করার জন্য তোকে পুরা array টা ঘুরা লাগে নাই। জাস্ট ওই পজিশনে গিয়ে, অর্থাৎ জায়গামতো গিয়ে পেয়ে গেছস। তাই এইটার জন্য ১টা জায়গায় যাওয়া লাগবে। তাই কোন একটা array থেকে কোন একটা নিদৃস্ট পজিশনের উপাদান বের করতে হলে একবার কোড চালানো লাগবে তাই এইটার time complexity হবে O(1)

সার্চ এলগোরিদম

তুই যদি কোন একটা array এর মধ্যে নিদৃষ্ট পজিশনের কাউকে বের না করে, কোন একটা উপাদান আছে কিনা জানতে চাস। তখন তোকে প্রথম উপাদান থেকে শুরু করতে হবে। তারপর একটা একটা করে সামনে আগাইতে আগাইতে দেখতে হবে সেটা আছে কিনা। তারমানে কোন কিছু খোঁজার জন্য তোকে সবগুলা উপাদানের একটা একটা করে দেখতে হয়। সেটার জন্য নিচের মতো করে কোড লিখস


var choukirTola = ["tShirt", "jeans", "juta", "boi", "gamcha", "charger", "panjabi"];
for(var i = 0; i < choukirTola.length; i++){
      var jinish = choukirTola[i];
      if( jinish == "charger"){
           console.log("charger paisi");
           break;
      }
}

উপরের কোড যেহেতু তুই সবগুলা উপাদান খুজস। আর আর array এর মধ্যে কয়টা উপাদান আছে সেটাকে সাধারণভাবে বললে বলা যায় n সংখ্যক উপাদান আছে। তাই

Sort এলগোরিদম:

Selection Sort এর কোড দেখছিলি? না দেখলে এইখানে থেকে দেখে আয়।

নিচে Selection Sort এর কোড দেখানো আছে। এই কোডের আগা-মাথা কিচ্ছু না বুঝতে পারলেও এক নজর দেখ। দেখবি একটা for লুপের ভিতরে আরেকটা for লুপ আছে।


function selectionSort(arr){
  var minIdx, temp,
      len = arr.length;
  for(var i = 0; i < len; i++){
    minIdx = i;
    for(var  j = i+1; j<len; j++){
       if(arr[j]<arr[minIdx]){
          minIdx = j;
       }
    }
    temp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
  }
  return arr;
}

তুই জানস, একটা for লুপের জন্য সবগুলা উপাদান একবার একবার করে চলে। তারমানে চারটা উপাদান থাকলে চারবার চলবে। তারমানে array এর মধ্যে যতগুলা উপাদান আছে, ততবার ভিতরের কোডগুলা চলবে। এখন ধর, একটা উপাদানের জন্য কোড for লুপের ভিতরে গেল। এখন ভিতরে গিয়ে দেখলো আরেকটা লুপ। এখন ভিতরের যেহেতু একটা লুপ, তাই ভিতরের লুপের জন্য সেই লুপ array এর যতগুলা উপাদান আছে, ততবার চলবে।

তারমানে বাইরের লুপের একটা উপাদানের জন্য ভিতরের লুপে যতগুলা উপাদান আছে ততবার চলবে। ধর, ভিতরের array এর মধ্যে n সংখ্যক উপাদান আছে। তাই ভিতরে লুপ n বার চলবে। আর যদি বাইরের লুপে দুইটা উপাদান থাকে, তাহলে বাইরের লুপের প্রথম উপাদানের জন্য ভিতরে গিয়ে, ভিতরের লুপ n বার চলবে। আবার বাইরের লুপের দ্বিতীয় উপাদানের জন্য ভিতরের লুপ n বার চলবে। তারমানে ভিতরের লুপ, দুইবার n সংখ্যকবার চলবে। এই দুইবার n সংখ্যকবার চলাকে লিখতে পারস ২n

আর যদি বাইরের array এর মধ্যে 3টা উপাদান থাকে, তাহলে ভিতরে গিয়ে, বাইরের লুপের প্রত্যেকটা উপাদানের জন্য n সংখ্যকবার চলে। মোট 3n বার চলবে।

তারমানে বাইরের লুপে একটা উপাদান থাকলে ভিতরের লুপ n বার। বাইরের লুপে 2টা উপাদান থাকলে ভিতরের লুপ 2n বার। আর বাইরের লুপে 3টা উপাদান থাকলে ভিতরের লুপ 3n বার চলবে। আর যদি বাইরের লুপে n সংখ্যক উপাদান থাকে তাহলে ভিতরের লুপ nXn বা n² বার চলবে।

তাই একটা লুপের ভিতরের আরেকটা লুপ থাকলে সেই কোডের টাইম কমপ্লেক্সিটি হয় O(n²)

আপাতত এইটুক মনে রাখতে পারলেই হবে।

Time Complexity