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

টাইম কমপ্লেক্সিটি শুনে আমাদের প্রথমে মনে হতে পারে, আমাদের কোড রান হতে কত সময় নেয় তার একটি ম্যাজারমেন্ট। ব্যাপারটি আসলে তা না। একটি কোড রান হতে কত সময় লাগছে তা আমরা কখনো হিসাব করি না। কারন সেইম কোড উইন্ডোজে রান করতে যত সময় লাগছে ম্যাক এ রান হতে তত সময় নাও লাগতে পারে। আবার 32-bit উইন্ডোজে যত সময় লাগছে 64-bit উইন্ডোজে হয়তো তার থেকে কম লাগতে পারে। এখন তাহলে আমরা কিভাবে পরিমাপ করব কোন কোডটি ফাস্ট এবং কোন কোডটি স্লো। এই পরিমাপটিই হচ্ছে টাইম কমপ্লেক্সিটি। টাইম কমপ্লেক্সিটিতে আমরা ইনপুট এর প্রেক্ষিতে অপারেশন নাম্বার কিরকম হতে পারে তা ম্যাজার করি।

আমাদের কোডটি যদি হয় এরকমঃ

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

এক্ষেত্রে ইনপুট n এর মান যদি ১০ হয় তাহলে কোডটি ১০বার হ্যালো প্রিন্ট করবে। অর্থাৎ ১০ বার প্রিন্ট অপারেশন চালাবে। তেমনি ইনপুট n এর মান যদি ১০০০০০০ (১০ লক্ষ বার) হয় তাহলে কোডটি ১০ লক্ষ বার হ্যালো প্রিন্ট করবে। এইযে ইনপুট এর মানের সাথে কোডের অপারেশনের একটি সম্পর্ক এটিই পরিমাপ করা হয় টাইম কমপ্লেক্সিটিতে।

Asymptotic Notation: টাইম কমপ্লেক্সিটির একক বলা যায় Asymptotic Notation কে। মূলত ৩ ধরনের Asymptotic Notation রয়েছে। - Big O Notation - Worst case - Theta Notation - Average case - Omega Notation - Best case

মনে করি আমার কাছে ১০০টি সংখ্যা রয়েছে। সেখান থেকে আমি একটি নির্দিষ্ট সংখ্যাকে খুজছি। তাহলে অবশ্যই আমাকে প্রথম থেকে এক এক করে সবগুলো সংখ্যা খুজে দেখতে হবে। এখন আমি যদি প্রথম বার খুজতে যেয়েই আমার কাংখিত সংখ্যাটি পেয়ে যাই তাহলে সেটিকে বেস্ট কেস বলা যায়। আমি যদি ৫০বার খুজার পর আমার সংখ্যাটি পাই তাহলে এভারেজ কেস বলতে পারি। এবং আমি যদি সবগুলো সংখ্যা খুজা শেষে (১০০ বার) একদম লাস্টে যেয়ে আমার সংখ্যাটি পাই তাহলে সেটিকে worst কেস বলা যেতে পারে।

টাইম কমপ্লেক্সিটি ক্যালকুলেট করার সময় আমরা সবসময় worst কেসটা নেই।

টাইম কমপ্লেক্সিটি কেন প্রয়োজনঃ মনে করি, আমরা দুজন স্টুডেন্টকে একটি প্রবলেম দিলাম। প্রবলেমটি হলো ১ থেকে n পর্যন্ত যোগ করতে হবে। এখন একজন স্টুডেন্ট n ইনপুট নেওয়ার পর ১ থেকে n পর্যন্ত লুপ চালিয়ে যোগফল বের করল। আরেকজন স্টুডেন্ট n*(n+1)/2 ( ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যার যোগফল এর সূত্র) দিয়ে করে ফেলল। এখন আমাদের যদি বের করতে হয় কার কোডটি বেটার, তাহলে আমাদের দুজনের কোডের কমপ্লেক্সিটি বের করতে হবে। এক্ষেত্রে দুজনের কোডই কারেক্ট আন্সার দিবে কিন্তু প্রথম স্টুডেন্ট এর কোড n পর্যন্ত লুপ চালিয়ে যোগ করবে। n এর মান যদি হয় ১০,০০০ তাহলে প্রথম স্টুডেন্ট এর কোড ১০,০০০টি অপারেশন চালাবে। অপরদিকে দ্বিতীয় স্টুডেন্ট, যে সূত্র দিয়ে করেছে তার কোড মাত্র ১টি অপারেশন চালাবে। অবশ্যই দ্বিতীয় স্টুডেন্ট এর কোড বেটার। এটি আমরা বলতে পারলাম টাইম কমপ্লেক্সিটির সাহায্যে।