Basic DSA Handbook

বাংলা

English

বাংলা

English

Appearance

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

“বাদ দেন ভাই? কী দরকার এইগুলা।
তাহলে আপনাদের একটা গল্প বলি। পড়তে পারেন যাতে আমাদের মতো অবস্থা না হয়। তো অনেক আগে আমি আর আমার এক বন্ধু Dhaka তে গিয়েছিলাম । রবীন্দ্র সরোবর থেকে Rifles Square যাব একটা ফুড আইটেম চেক করতে। তো আমরা দুইজনেই চিনি না, তাই ভরসা করলাম গুগল ম্যাপের উপর। তো গুগল ম্যাপ আমাদেরকে পুরো একটা চক্কর দিয়ে আবার একই জায়গায় নিয়ে আসছে । ফলাফল সময় নষ্ট আর আমাদের অবস্থা ছিল "এ কেমন বিচার গুগল ম্যাপের?" তারপর আমরা ম্যাপটা ভালোমতো দেখলাম। Destination চেক করে দেখলাম যে ওইখানে একটা রাস্তা শর্টেস্ট ওয়ে তে যেয়ে মিলেছে। এরপর আমরা ম্যাপের সাজেশন করা রাস্তা না দেখে সরাসরি সেই শর্টকাট নিলাম এবং সহজেই সেখানে পৌঁছে গেলাম। এরপর থেকে কখনো গুগল ম্যাপের সাহায্য লাগলে আগে শর্টকাটে কোন পথ যাওয়া যায় সেটা দেখতাম। এখানে যদি লক্ষ্য করেন, গুগল ম্যাপ আমাদেরকে পুরো একটা লুপে ফেলে দিয়েছিল, কিন্তু তাও আমরা গন্তব্য স্থানে যেতে পারিনি। যদি যেতেও পারতাম, তারপরও সেটা এফিশিয়েন্ট উপায়ে নাও হতে পারতো । দ্বিতীয়বার আমরা রাস্তাটা এনালাইজ করে শর্টকাটে গেছি — আর ঠিক এখানেই আসে Time Complexity এর ব্যাপারটা। প্রথমবার আমরা বেশি সময় লাগানো একটা path নিয়েছিলাম (higher time complexity) আর দ্বিতীয়বার বুঝে শুনে কম সময়ে যাওয়ার রাস্তা বেছে নিয়েছিলাম (lower time complexity)। Algorithm ডিজাইনেও তাই কাজটা শুধু হওয়াই যথেষ্ট নয়, সেটা কত অপারেশন, সময় ও resource-এ হচ্ছে সেটাও গুরুত্বপূর্ণ ।

টাইম ও স্পেস কমপ্লেক্সিটি কী? ​

  • টাইম কমপ্লেক্সিটি: একটি অ্যালগোরিদম ইনপুট সাইজ (n) অনুযায়ী কত অপারেশন বা স্টেপ করে, সেটার একটি পরিমাপ। এটি বাস্তব সময় নয়, বরং বোঝায় ইনপুট বাড়লে অ্যালগোরিদমের কাজ কত বাড়ে ।

  • স্পেস কমপ্লেক্সিটি: একটি অ্যালগোরিদম চালাতে কত অতিরিক্ত মেমোরি (RAM) প্রয়োজন হয়, ইনপুট সাইজের উপর ভিত্তি করে — সেটার পরিমাপ।

টাইম কমপ্লেক্সিটি আসলে কী? ​

টাইম কমপ্লেক্সিটি বাস্তব সময় (real time) নয়, বরং একটি অ্যালগোরিদম চালাতে কতগুলো স্টেপ বা অপারেশন লাগে সেটার একটি পরিমাপ।

ধরা যাক, একটি অ্যালগোরিদমে প্রতি ইনপুট আইটেমের জন্য একটি লুপ চলে — তাহলে:

  • ১০টি ইনপুটে ১০টি স্টেপ,
  • ১০০টি ইনপুটে ১০০টি স্টেপ লাগবে।

ইনপুট যত বড় হয়, অ্যালগোরিদমকে তত বেশি অপারেশন বা কাজ করতে হয়।
এই কাজ বা স্টেপের সংখ্যাকেই আমরা টাইম কমপ্লেক্সিটি দিয়ে প্রকাশ করি।

যেমন :

cpp
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cout << i << endl;
    }

    return 0;
}

এই লুপটি n বার চলে, তাই এর টাইম কমপ্লেক্সিটি হলো O(n)।

আমরা যদি এই কোডটি একটি সাধারণ ল্যাপটপে চালাই অথবা একটি সুপারকম্পিউটারে চালাই সেক্ষেত্রে এক্সিকিউশন টাইম কম-বেশি লাগতে পারে,
কারণ যন্ত্রভেদে প্রসেসরের গতি, RAM ইত্যাদি ভিন্ন হয়।

তবে, স্টেপ সংখ্যা n সব ক্ষেত্রেই অপরিবর্তিত থাকবে।

টাইম কমপ্লেক্সিটিতে মূলত দেখা হয় —
ইনপুট বাড়লে অ্যালগোরিদমের কাজের পরিমাণ কত দ্রুত বাড়ছে।

এই বৃদ্ধির হারকেই বলা হয় গ্রোথ রেট (Growth Rate)।

অ্যাসিম্পটোটিক নোটেশন ( Asymptotic Notation ) ​

অ্যাসিম্পটোটিক নোটেশন হল অ্যালগোরিদমের কমপ্লেক্সিটি প্রকাশ করার একটি নিয়ম, যাতে ইনপুট বড় হলে সেই অ্যালগোরিদম কত দ্রুত বা ধীরে কাজ করবে তা বুঝা যায় ।

মূলত তিন ধরনের অ্যাসিম্পটোটিক নোটেশন রয়েছে:

  • Big-O Notation (O-notation) ( বিগ-ও নোটেশন ) - worst case
  • Omega Notation (Ω-notation) ( ওমেগা নোটেশন ) - best case
  • Theta Notation (Θ-notation) ( থীটা নোটেশন ) - average case

এই বিষয়ে আরো জানতে চাইলে এইখানে দেখে আস্তে পারেন ।

Big-O নোটেশন কীভাবে বুঝি? ​

Big-O হচ্ছে অ্যালগোরিদমের পারফরম্যান্স বোঝানোর জন্য একটা সাধারণ মান। Big-O দিয়ে আমরা worst-case scenario বোঝাই । এর মাধ্যমে সবচেয়ে খারাপ পরিস্থিতিতে কতোগুলো অপারেশন বা জায়গা লাগবে, সেটা আমরা বুঝতে পারি ।

যেমনঃ

O(1) এর একটা উদাহরণ দেখিঃ

cpp

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    cout << a << endl; // সবসময় একবারই চলবে
}

টাইম কমপ্লেক্সিটি কিভাবে বের করবো? ​

প্রতিটি লুপ, ফাংশন কল ইত্যাদির ওপর নির্ভর করে টাইম কমপ্লেক্সিটি বের করা হয়।

আমরা সাধারণত টাইম কমপ্লেক্সিটি বর্ণনা করি ইনপুটের ওপর ভিত্তি করে, যেখানে n হলো ইনপুটের সাইজ ।

টাইম কমপ্লেক্সিটি = ইনপুট বৃদ্ধিতে অপারেশন বৃদ্ধির হার

ধাপঃ

  1. যতবার অপারেশন চলছে, সেটার সংখ্যা গণনা করো

  2. ধ্রুবক ও ছোট পদ বাদ দিয়ে বড় অংশ রাখো

  3. শেষে Big-O আকারে লেখা

লিনিয়ার কমপ্লেক্সিটি - Linear Complexity O(n) ​

ইনপুট (n) যত বাড়ে, অপারেশনের সংখ্যা ঠিক ততটাই বাড়ে।

Example:

cpp

for(int i = 0; i < n; i++) {
    cout << i << endl;
}

যদি n এর মান 10 হয় তাহলে লুপ 10 বার চলবে। যদি 20 হয় তাহলে 20 বার । তাই এখানে n যতো বাড়ে অপারেশনের সংখ্যা ঠিক ততটাই বাড়ে ।

লগারিদমিক কমপ্লেক্সিটি - Logarithmic Complexity O(log n) ​

যখন লুপের increment বা decrement এমন হয় যে প্রতি ধাপে আপনার কাজের পরিমাণ গুণ (multiply) হয়ে হয়ে বাড়ে বা ভাগ (divide) হয়ে হয়ে কমে, তখন সেই লুপের complexity সাধারণত হয় logarithmic complexity (log n)।

কেন?

ধরুন, একটা লুপে i প্রতি ধাপে ২ দিয়ে গুণ হচ্ছে, যেমন: i = i * 2 তাহলে i হবে 1, 2, 4, 8, 16 ... এইভাবে বৃদ্ধি পাবে। এই লুপ কতবার চলবে? প্রায় log₂(n) বার, কারণ i যখন n এর সমান বা বড় হবে তখন লুপ থামবে।

অথবা লুপে i প্রতি ধাপে ২ দিয়ে ভাগ হচ্ছে: i = i / 2 তাহলে i হবে n, n/2, n/4, n/8 ... আবার লুপ চলবে প্রায় log₂(n) বার।

অন্যদিকে, যদি লুপে increment বা decrement শুধু +1 বা -1 হয় (মানে প্রতি ধাপে এক করে বাড়ে বা কমে), তখন complexity হবে linear, অর্থাৎ O(n)।

Example:

cpp

for (int i = 1; i <= n; i = i * 2) {
    
}

// or

for (int i = 1; i <= n; i = i / 1) {
    
}

স্কয়ার রুট কমপ্লেক্সিটি - Square Root Complexity O(√n) ​

ইনপুট n হলে অপারেশন হয় √n বার

Example:

cpp

for(int i = 1; i <= sqrt(n); i++) {
    cout << i << " ";
}

// অথবা এই একই কোড আমরা এইভাবেও লিখতে পারি
for(int i = 1; i * i <= n; i++) {
    cout << i << " ";
}

যদি n = 100 হয় তাহলে √100 = 10 মানে লুপটি 10 বার চলবে।

কোয়াড্রাটিক কমপ্লেক্সিটি - Quadratic Complexity O(n × n) বা O(n²) ​

মানে: এক লুপের ভিতরে আরেকটা লুপ নেস্টেড আকারে থাকলে — n × n বার অপারেশন হয়। ইনপুট একটু বড় হলেই কোড অনেক ধীর হয়ে যায়।

Example:

cpp

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        cout << i << "," << j << endl;
    }
}

যদি n এর মান 10 হয় তাহলে 10 × 10 = 100 বার অপারেশন হবে ।

লিনিয়ারিথমিক কমপ্লেক্সিটি - Linearithmic Complexity O(n log n) ​

যখন প্রতিটি আইটেম নিয়ে log n টাইপ কাজ করতে হয়, তখন কমপ্লেক্সিটি হয় O(n log n), যেটাকে বলা হয় Linearithmic Complexity।

  • যদি কেবল n থাকে, তখন সেটাকে বলা হয় Linear Complexity — O(n)
  • যদি কেবল log n থাকে, তখন সেটাকে বলা হয় Logarithmic Complexity — O(log n)
  • আর যখন দুইটাই একসাথে থাকে, অর্থাৎ n * log n, তখন সেটাই হয় Linearithmic Complexity — O(n log n)

Example:

cpp
// নিচের লুপের কমপ্লেক্সিটি: O(n log n)

for (int i = 0; i < n; i++) {          // O(n)
    for (int j = 1; j < n; j *= 2) {   // O(log n)
        cout << i << "," << j << endl;
    }
}

স্পেস কমপ্লেক্সিটি ( Space Complexity ) কী? ​

একটা কোড চলাকালীন সময়ে কতটা জায়গা বা মেমরি লাগছে — সেটাই স্পেস কমপ্লেক্সিটি ।

দুই ধরনের মেমরি ব্যবহার হয়:

Fixed Space

  • যেমন: ভ্যারিয়েবল, কনস্ট্যান্ট, লুপ কাউন্টার ইত্যাদি।
  • এগুলো ইনপুট সাইজের উপর নির্ভর করে না।

Dynamic Space (Variable Space)

  • যেমন: অ্যারে, রিকার্সন কল, ইনপুট ডেটা ইত্যাদি।
  • এগুলো ইনপুট সাইজের উপর নির্ভর করে।

Example 1:

cpp

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;
}

এখানে কোনো নতুন অ্যারে বা অতিরিক্ত জায়গা লাগেনি। শুধু কিছু সংখ্যা রাখতে হয়েছে

Space Complexity = O(1)

Example 2:

cpp

int arr[n];
for (int i = 0; i < n; i++) {
    cin >> arr[i];
}

এখানে arr[n] নামে একটি অ্যারে নিয়েছি।

ইনপুট সাইজ n তাই n সংখ্যক জায়গা লাগছে।

Space Complexity = O(n)

সামারি ​

  • টাইম কমপ্লেক্সিটি বোঝায় হলো ইনপুট বড় হলে অ্যালগোরিদম কতগুলো ধাপ বা কাজ করে

  • স্পেস কমপ্লেক্সিটি বোঝায় অ্যালগোরিদম চালাতে কত মেমোরি বা জায়গা লাগে।

  • টাইম কমপ্লেক্সিটি বিশ্লেষণ করতে আমরা Big-O নোটেশন ব্যবহার করি, যা কোনো অ্যালগরিদমের worst-case scenario সম্পর্কে ধারণা দেয়।

  • টাইম কমপ্লেক্সিটির সাধারণ বিষয় গুলো হলো:

    • O(1) — Constant (যেমন: সরাসরি ভ্যালু এক্সেস)
    • O(n) — Linear (একটা সাধারণ লুপ)
    • O(log n) — Logarithmic (increment বা decrement পার্ট multiply হয়ে হয়ে বা divide হয়ে হয়ে চলে)
    • O(n log n) — Linearithmic
    • O(n²) — Quadratic (nested loop)
    • O(√n) — Square Root (sqrt-based loop)

  • স্পেস কমপ্লেক্সিটি বিশ্লেষণে বিবেচনা করা হয়:

    • Fixed variables → O(1)
    • Input-based array/data structure → O(n)

আরও পড়ার লিঙ্ক ​