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

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

১. আমার অ্যালগোরিদম কি নির্ধারিত সময়ের মধ্যে ফলাফল এনে দিবে?
২. সর্বোচ্চ কত বড় ইনপুটের জন্য আমার অ্যালগোরিদম কাজ করবে?

আমরা অ্যালগরিদমের কমপ্লেক্সিটি বের করে প্রথম দুটি প্রশ্নের উত্তর দিতে পারি। একটি অ্যালগরিদম যতগুলো “ইনস্ট্রাকশন” ব্যবহার করে কাজ করে সেটাই সোজা কথাই সেই অ্যালগোরিদমের কমপ্লেক্সিটি। দুটি নম্বর গুণ করা একটি ইনস্ট্রাকশন, আবার একটি লুপ ১০০ বার চললে সেখানে আছে ১০০টি ইনস্ট্রাকশন। ফলাফল আসতে কতক্ষণ লাগবে সেটা সিপিউর প্রসেসরের উপর নির্ভর করবে, কমপ্লেক্সিটি আমাদের cputime বলে দিবেনা, কমপ্লেক্সিটি আমাদের বলে দিবে আমাদের অ্যালগরিদমটি তুলনামূলকভাবে কতটা ভালো। অর্থাৎ এটা হলো অ্যালগরদিমের কার্যকারিতা নির্ধারণের একটা স্কেল। 

আর BIG O

$O$

নোটেশন হলো কমপ্লেক্সিটি লিখে প্রকাশ করার নোটেশন।

আমরা একটা উদাহরণ দিয়ে শুরু করি।

#include <stdio.h> int main () { int n1, n2, retult; n1 = 10; n2 = 20; result = n1 + n2; }

এই অ্যালগোরিদমটি $\mathrm{n1,\; n2}$ এর ভ্যালু যাই হোকনা কেন সবসময় একটি constant সংখ্যক ইনস্ট্রাকশন নিয়ে কাজ করবে। কোডটিকে মেশিন কোডে পরিণত করলে যোগ-ভাগ মিলিয়ে ৫-৬ ইনস্ট্রাকশন  পাওয়া যাবে,আমাদের সেটা নিয়ে ম্যাথাব্যাথার দরকার নাই। প্রসেসর এত দ্রুত কাজ করে যে এত কম ইনস্ট্রাকশন নিয়ে কাজ করতে যে সময় লাগে সেটা নিয়ে আমরা চিন্তাই করিনা,ইনস্ট্রাকশন অনেক বেশি হলে আমরা চিন্তা করি,আর লুপ না থাকলে সাধারণত চিন্তা করার মত বেশি হয়না।

অ্যালগোরিদমের কমপ্লেক্সিটি হলো $O\left(1\right)$,এর মানে হলো ইনপুটের আকার যেমনই হোকনা কেন একটি constant টাইমে অ্যালগোরিদমটি কাজ করা শেষ করবে।

এবার পরের কোডটি দেখা যাকঃ 

int i, n, result; scanf("%d" , &n); result = 0; for(i = 0; i <= n; i++) { result = result + i; }

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

ক্ষেত্রে কোডের কমপ্লেক্সিটি হবে  $O$$($$n$$)$

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

উপরের কোডে ভিতরের লুপটা প্রথমবার $n$ বার চলছে,পরেরবার $n-1$ বার। তাহলে মোট লুপ চলছে $n+(n-1)+(n-3)+\dots \dots .+1=n\times (n+1)/2=(n^2+n)/2$ বার। $n^2$ এর সাথে $n^2+n$ এর তেমন কোনো পার্থক্য নেই। আবার $n^2/2$ এর সাথে $n^2$ এর পার্থক্যও খুব সামান্য। তাই কমপ্লেক্সিটি হবে $O\left(n^2\right)$।

কমপ্লেক্সিটি হিসাবের সময় constant factor গুলোকে বাদ দিয়ে দিতে হয়। তবে কোড লেখার সময় constant factor এর কথা অবশ্যই মাথায় রাখতে হবে।

উপরের ৩টি অ্যালগোরিদমের মধ্যে সবথেকে সময় কম লাগবে কোনটির? অবশ্যই $O\left(1\right)$ এর সময় কম লাগবে এবং $O\left(n^2\right)$ এর বেশি লাগবে। এভাবেই কমপ্লেক্সিটি হিসাব করে অ্যালগোরিদমের কার্যকারিতা তুলনা করা যায়। পরের কোডটি দেখা যাক ঃ

int binary_search(int n,int val,int key) { int low=1,high=n; while(low<=high) { int mid = low + (high - low)/2; if(key<val[mid]) low=mid-1; if(key>val[mid]) high=mid+1; if(key==val[mid]) return 1; } return 0; }

এটা একটা বাইনারি সার্চের কোড। প্রতিবার $low+high=n+1$ বা $n$ এর মান দুই ভাগে ভাগ হয়ে যাচ্ছে। একটি সংখ্যাকে সর্বোচ্চ কতবার ২দিয়ে ভাগ করা যায়? একটি হিসাব করলেই বের করতে পারবে সর্বোচ্চ ভাগ করা যাবে $lo{g}_{2}n$ বার। তারমানে $lo{g}_{2}n$ ধাপের পর লুপটি ব্রেক করবে। তাহলে কমপ্লেক্সিটি হবে $O\left(lo{g}_{2}n\right)$।

$f\left(n\right)$=ইনস্ট্রাকশন সংখ্যা
$f\left(n\right)=n^2+\; n\; +3n+10$ হলে কমপ্লেক্সিটি $O\left(n^2\right)$।
$f\left(n\right)=n^3+\mathrm{n\; +\; 999}n+112$ হলে কমপ্লেক্সিটি $O\left(n^3\right)$।
$f\left(n\right)=6\times log\left(n\right)+n\times logn$ হলে কমপ্লেক্সিটি $O(n\times logn)$।

আরেকটি কমন ভুল হলো এভাবে কোড লেখা:

for(int i=0;i<strlen(s);i++) { if(s[i]=='a') c++; } return c;

s স্ট্রিং এর দৈর্ঘ্য s হলে এখানে কমপ্লেক্সিটি হলো $O\left(s{}^2\right)$। কেন স্কয়ার হলো? কারণ strlen(s) ফাংশনের নিজের কমপ্লেক্সিটি হলো $O(s)$,একে লুপের মধ্যে আরো $O(s)$ বার কল করা হয়েছে। তাই strlen(s) এর মান আগে অন্য একটি ভ্যারিয়েবলের রেখে তারপর সেটা দিয়ে লুপ চালাতে হবে,তাহলে $O(s)$ এ লুপ চলবে।

নিচের গ্রাফে বিভিন্ন কমপ্লেক্সিটির অ্যালগোরিদমের তুলনা দেখানো হয়েছে:

               
                                                                       ©  Wikipedia