Skip to main content

টাইম কমপ্লেক্সিটি By Zhakaria Shikder

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

 
১. আমার অ্যালগোরিদম কি নির্ধারিত সময়ের মধ্যে ফলাফল এনে দিবে?
২. সর্বোচ্চ কত বড় ইনপুটের জন্য আমার অ্যালগোরিদম কাজ করবে?
৩. আমার অ্যালগোরিদম কতখানি মেমরি ব্যবহার করছে?
আমরা অ্যালগোরিদমের কমপ্লেক্সিটি বের করে প্রথম দুটি প্রশ্নের উত্তর দিতে পারি। একটি অ্যালগোরিদম যতগুলো “ইনস্ট্রাকশন” ব্যবহার করে কাজ করে সেটাই সোজা কথাই সেই অ্যালগোরিদমের কমপ্লেক্সিটি। দুটি নম্বর গুণ করা একটি ইনস্ট্রাকশন, আবার একটি লুপ ১০০ বার চললে সেখানে আছে ১০০টি ইনস্ট্রাকশন। ফলাফল আসতে কতক্ষণ লাগবে সেটা সিপিউর প্রসেসরের উপর নির্ভর করবে, কমপ্লেক্সিটি আমাদের cputime বলে দিবেনা, কমপ্লেক্সিটি আমাদের বলে দিবে আমাদের অ্যালগোরিদমটি তুলনামূলকভাবে কতটা ভালো। অর্থাৎ এটা হলো অ্যালগোরদিমের কার্যকারিতা নির্ধারণের একটা স্কেল। আর BIG “O” নোটেশন হলো কমপ্লেক্সিটি লিখে প্রকাশ করার নোটেশন।
নতুন প্রোগ্রামিং কনটেস্টেন্টরা প্রায়ই কমপ্লেক্সিটির ব্যাপারে খেয়াল না করেই ব্রুট-ফোর্স অ্যালগোরিদম লিখে ফেলে এবং কোড time limit exceed করে। আর যারা শুধুমাত্র সফটওয়্যার নিয়ে কাজ করে তাদের মধ্যে কমপ্লেক্সিটি নিয়ে চিন্তা করার প্রবণতা আরো কম। এই লেখাটা বিগিনার প্রোগ্রামারদের জন্য যারা এখনো সঠিকভাবে কমপ্লেক্সিটি হিসাব করা শিখেনি।
আমরা একটা উদাহরণ দিয়ে শুরু করি। আমাদের একটি ফাংশন আছে যার নাম myAlgorithm,আমরা সেই ফাংশনের কমপ্লেক্সিটি বের করবো। মনে করো ফাংশনটি এরকম:
 
int myAlgorithm1(int n){ int x=n+10; x=x/2; return x;}
 
 
int myAlgorithm1(int n)
{
    int x=n+10;
    x=x/2;
    return x;
}
এই অ্যালগোরিদমটি n এর ভ্যালু যাই হোকনা কেন সবসময় একটি constant সংখ্যক ইনস্ট্রাকশন নিয়ে কাজ করবে। কোডটিকে মেশিন কোডে পরিণত করলে যোগ-ভাগ মিলিয়ে ৩-৪ ইনস্ট্রাকশন পাওয়া যাবে,আমাদের সেটা নিয়ে ম্যাথাব্যাথার দরকার নাই। প্রসেসর এত দ্রুত কাজ করে যে এত কম ইনস্ট্রাকশন নিয়ে কাজ করতে যে সময় লাগে সেটা নিয়ে আমরা চিন্তাই করিনা,ইনস্ট্রাকশন অনেক বেশি হলে আমরা চিন্তা করি,আর লুপ না থাকলে সাধারণত চিন্তা করার মত বেশি হয়না।
অ্যালগোরিদমের কমপ্লেক্সিটি হলো O(1),এর মানে হলো ইনপুটের আকার যেমনই হোকনা কেন একটি constant টাইমে অ্যালগোরিদমটি কাজ করা শেষ করবে।
এবার পরের কোডটি দেখ:
int myAlgorithm2(int n){ int sum=0; for(int i=1;i=1000) break; } return sum;}
 
 
int myAlgorithm2(int n)
{
    int sum=0;
    for(int i=1;i
    {
        sum+=i;
                if(sum>=1000) break;
    }
    return sum;
}
এই কোডে একটি লুপ চলছে এবং সেটা n এর উপর নির্ভরশীল। n=100 হলে লুপ ১০০ বার চলবে। লুপের ভিতরে বা বাইরে কয়টি ইনস্ট্রাকশন আছে সেটা নিয়ে চিন্তা করবোনা,কারণ সেটার সংখ্যা খুবই কম। উপরের অ্যালগোরিদমের কমপ্লেক্সিটি O(n) কারণ এখানে লুপটি n বার চলবে। তুমি বলতে পারো sum যদি ১০০০ এর থেকে বড় হয় তাহলে break করে দিচ্ছি, n পর্যন্ত চলার আগেই লুপটি break হয়ে যেতে পারে। কিন্তু প্রোগ্রামাররা সবসময় worst case বা সবথেকে খারাপ কেস নিয়ে কাজ করে! এটা ঠিক যে লুপটি আগে break করতেই পারে,কিন্তু worst case এ সেটা n পর্যন্তইতো চলবে।
worst case এ যতগুলো ইনস্ট্রাকশন থাকবে সেটাই আমাদের কমপ্লেক্সিটি।
int myAlgorithm3(int n){ int sum=0; for(int i=1;i
 
int myAlgorithm3(int n)
{
    int sum=0;
    for(int i=1;i
    {
        for(int j=i;j
        {
            sum+=(i+j);
        }
    }
    return sum;
}
উপরের কোডে ভিতরের লুপটা প্রথমবার n বার চলছে,পরেরবার n-1 বার। তাহলে মোট লুপ চলছে n+(n-1)+(n-3)+…….+1 = n*(n+1)/2 = (n^2+n)/2 বার। n^2 এর সাথে n^2+n এর তেমন কোনো পার্থক্য নেই। আবার n^2/2 এর সাথে n^2 এর পার্থক্যও খুব সামান্য। তাই কমপ্লেক্সিটি হবে O(n^2)।
কমপ্লেক্সিটি হিসাবের সময় ছোটখাট constant গুলো আমরা বাদ দিয়ে দিতে পারি। তবে constant যদি ১০ এর বড় হয় তাহলে সেটা অবশ্যই আমাদের মাথায় রাখতে হবে।
উপরের ৩টি অ্যালগোরিদমের মধ্যে সবথেকে সময় কম লাগবে কোনটির? অবশ্যই O(1) এর সময় কম লাগবে এবং O(n^2) এর বেশি লাগবে। এভাবেই কমপ্লেক্সিটি হিসাব করে অ্যালগোরিদমের কার্যকারিতা তুলনা করা যায়। পরের কোডটি দেখো:
 
int myAlgorithm4(int n,int *val,int key){ int low=1,high=n; while(lowval[mid]) high=mid+1; if(key==val[mid]) return 1; } return 0;}
 
 
int myAlgorithm4(int n,int *val,int key)
{
    int low=1,high=n;
    while(low
    {
        int mid=(low+high)/2;
        if(key
        if(key>val[mid]) high=mid+1;
        if(key==val[mid]) return 1;
    }
    return 0;
}
এটা একটা বাইনারি সার্চের কোড। প্রতিবার low+high=n+1 বা n এর ভ্যালু দুই ভাগে ভাগ হয়ে যাচ্ছে। একটি সংখ্যাকে সর্বোচ্চ কতবার ২দিয়ে ভাগ করা যায়? একটি হিসাব করলেই বের করতে পারবে সর্বোচ্চ ভাগ করা যাবে log2(n) বার। তারমানে log2(n) ধাপের পর লুপটি ব্রেক করবে। তাহলে কমপ্লেক্সিটি হবে O(logn)।
 
এখন ধরো একটি অ্যালগোরিদমে কয়েকটি লুপ আছে,একটি n^4 লুপ আছে,একটি n^2 লুপ আছে আর একটি logn লুপ আছে। তাহলে মোট ইনস্ট্রাকশন: n^4+n^3+logn টি। কিন্তু n^4 এর তুলনায় বাকি টার্মগুলো এতো ছোটো যে সেগুলোকে বাদ দিয়েই আমরা কমপ্লেক্সিটি হিসাব করবো,O(n^4)।
রিকার্সিভ ফাংশনে depth এর উপর কমপ্লেক্সিটি নির্ভর করে,যেমন:
 
int myAlgorithm5(int n){ if(n==1) return 1; return n*myAlgorithm5(n-1);}
 
 
int myAlgorithm5(int n)
{
    if(n==1) return 1;
    return n*myAlgorithm5(n-1);
}
এই অ্যালগোরিদমে সর্বোচ্চ depth হলো n,তাই কমপ্লেক্সিটি হলো O(n)। নিচে ছোট করে আরো কিছু উদাহরণ দিলাম:
 
f(n)=ইনস্ট্রাকশন সংখ্যা
f(n) = n^2 + 3n + 112 হলে কমপ্লেক্সিটি O(n^2)।
f(n) = n^3 + 999n + 112 হলে কমপ্লেক্সিটি O(n^3)।
f(n) = 6log(n) + nlogn হলে কমপ্লেক্সিটি O(nlogn)।
f(n) = 2^n+n2+100 হলে কমপ্লেক্সিটি O(2^n)। (এটাকে exponential কমপ্লেক্সিটি বলে)
বিগিনারদের আরেকটি কমন ভুল হলো এভাবে কোড লেখা:
 
int myAlgorithm6(char *s){ int c=0; for(int i=0;i
 
 
int myAlgorithm6(char *s)
{
    int c=0;
    for(int i=0;i
    {
        if(s[i]=='a') c++;
    }
    return c;
}
s স্ট্রিং এর দৈর্ঘ্য |s| হলে এখানে কমপ্লেক্সিটি হলো O(|s|^2)। কেন স্কয়ার হলো? কারণ strlen(s) ফাংশনের নিজের কমপ্লেক্সিটি হলো O(|s|),একে লুপের মধ্যে আরো O(|s|) বার কল করা হয়েছে। তাই strlen(s) এর মান আগে অন্য একটি ভ্যারিয়েবলের রেখে তারপর সেটা দিয়ে লুপ চালাতে হবে,তাহলে O(|s|) এ লুপ চলবে।
প্রোগ্রামিং কনটেস্টে আমরা ধরে নেই জাজ এর পিসি ১ সেকেন্ডে মোটামুটি 10^8 টা ইনস্ট্রাকশন রান করতে পারবে। এটা জাজ-পিসি অনুসারে কমবেশি হতে পারে,যেমন টপকোডার আরো অনেক বেশি ইনস্ট্রাকশন ১ সেকেন্ডে রান করতে পারে কিন্তু spoj বা কোডশেফ তাদের পেন্টিয়াম ৩ পিসি দিয়ে 10^7 টাও সহজে রান করতে পারেনা। অনসাইট ন্যাশনাল কনটেস্টে আমরা ১ সেকেন্ডে 10^8 ধরেই কোড লিখি। কোড লেখার আগে প্রথমে দেখবে তোমার অ্যালগোরিদমের worst case কমপ্লেক্সিটি কত এবং টেস্ট কেস কয়টা এবং দেখবে টাইম লিমিট কত। অনেক নতুন প্রোগ্রামার অ্যালগোরিদমের কমপ্লেক্সিটি সঠিক ভাবে হিসাব করলেও টেস্ট কেস সংখ্যাকে গুরুত্ব দেয়না,এ ব্যাপারে সতর্ক থাকতে হবে।
নিচের গ্রাফে বিভিন্ন কমপ্লেক্সিটির অ্যালগোরিদমের তুলনা দেখানো হয়েছে:
 
(x axis=input size, y axis=number of instructions)
কনটেস্টে প্রবলেমের ইনপুট সাইজ দেখে অনেক সময় expected algorithm অনুমান করা যায়। যেমন n=100 হলে সম্ভাবনা আছে এটা একটা n^3 কমপ্লেক্সিটির ডিপি প্রবলেম,বা ম্যাক্সফ্লো-ম্যাচিং প্রবলেম। n=10^5 হলে সাধারণ nlogn কমপ্লেক্সিটিতে প্রবলেম সলভ করতে হয় তাই সম্ভাবনা আছে এটা একটা বাইনারি সার্চ বা সেগমেন্ট ট্রি এর প্রবলেম। n
 
........X.......
 
 
এলগরিদম কথন ( শুধু মাত্র C.S.E এর স্টুডেন্ট এর জন্য )
 
পাগলের পাগলামি মানুষের সাথে তবে আমার পাগলামি কম্পিউটার এর সাথে । আমার এই পাগলামি মানুষ বুঝে না , আমার কম্পু বুঝে । আমার পাগলামির কিছু নমুনা দেওয়া যাক । প্রথমত কম্পিউটার কাজ করে মিলি সেকেন্ডে , আমার একদিন শখ হলো কম্পিউটার এর ক্ষমতা পরিক্ষা করা । যেই কথা সেই কাজ । এলগোরিদম বইয়ে অনেক গুলো সর্টিং এর এলগোরিদম আছে যার মধ্যে Quick Sort এবং Marge Sort নামে দুটো সর্টিং খুব জনপ্রিয় । এই দুটো এলগোরিদম কে Java তে কোডিং করলাম ।
কোডিংটা ছিল এমন , এক হাজার Random সংখ্যাকে একবার Quick Sort আর একবার Marge Sort করা এবং System থেকে এই দুটো সর্টিং এর সময় নেয়া । এই দুইটা সময়ের পার্থক্য দিয়েই তাদের কার্যক্ষমতা বের করা ।
হ্যাঁ আমি বের করলাম যেটি সেটি হচ্ছে ১০০০০০ Random সংখ্যাকে Marge sort করলে Quick Sort থেকে ০.০২৬ সেকেন্ড কম সময় লাগে ( তবে কম সংখ্যক সংখ্যার জন্য টাইম এর তেমন পরিবর্তন দেখা যাবে না ) অর্থাৎ এটা থেকেই এলগরিদম এর কঠিন টপিক Complexity of Algorithm আমার কাছে অনেকটা পরিস্কার হয়ে গেল ।
এলগরিদম নিয়ে আরেকটি পাগলামি করলাম সেটা ছিল NQueen এলগরিদম দিয়ে । আগে একটু বলে নেই NQueen এলগরিদম টা হচ্ছে N টি Queen কে N সংখ্যক ঘরে রাখতে হবে যাতে করে দাবার Queen এর চালে কেউ কাউকে ধরতে না পারে ।
আমার চিন্তা হল এই প্রব্লেমটা দিয়ে তৈরি আমার C কোডিং সর্বোচ্চ কতটি Queen নিয়ে ফলাফল কত সময়ে দিতে পারে । যেই কথা সেই কাজ । প্রোগ্রামটি আরও Efficient করার জন্য কিছু পরিবর্তন আনলাম যেটা অবশ্যই এর নির্দেশিত এলগরিদম অনুসারে এবং ফলাফল দেখতে থাকলাম ।
ফলাফলে যেটি হল , Queen ২১টি হলে ফলাফল আসতে সময় লাগে ১০ সেকেন্ড এর মতো আর ২৯টি হলে সময় লাগে ১ মিনিট এর মতো । অবিশ্বাস্য হলেও সত্য আমার দেখা সবচেয়ে High Time CPU calculation ছিল এটি ।
কিছু নমুনা এর সাথে আরও যোগ করা যেত যেমন Android Application নিয়ে করা কিছু পাগলামি যা অন্য কোন একদিন শেয়ার করবো ।
শেষটা আমার এক স্যার এর গল্প দিয়ে হোক , স্যার বলতেন প্রাক্টিকাল খাতার সতর্কতা সবার আগে লেখা উচিৎ কারন এই সতর্কতা যদি কেউ না জানে তবে তো সে প্রাকটিকালি সবকিছু নষ্ট করে ফেলবে । সেই জন্যই সতর্কতা সবার শুরুতে দিলাম ।

Comments

Post a Comment

Popular posts from this blog

NT Part 1:GCD, LCM, Euclidean Algorithm

  The definitions of GCD and LCM are well-known, (and taught in middle school I think) I will skip the definitions. Also, since  ,  calculating GCD is equivalent to calculating LCM. Now, how do we calculate the GCD of two numbers? A naive solution would be iterating over all positive integers no more than  . This will get the GCD in  ,  very very slow. We can calculate the GCD of   in   using Euclidean Algorithm. This algorithm uses the easy-to-prove fact  ,  where   is the remainder when   is divided by  ,  or just a%b. We can now use the following code. #include <iostream> using namespace std ; int gcd ( int u, int v ) { return u % v == 0 ? v : gcd ( v,u % v ) ; } int main ( void ) { int x, y ; cin >> x >> y ; cout << gcd ( x,y ) ; } How do we prove that this algorithm is  ?  Well, let's suppose that we started with  . Then...
Post a Comment
Read more

NT Part 4: Mobius Function Part 1. The Introduction

  What is mobius function? This function is notated as  .  This function has lots of definitions. However, the main definition is the following.  is   if   or   is square-free and has even number of prime divisors.  is   if   is square-free and has odd number of prime divisors.  is   if   is not square-free.  also has a lot of interesting properties that make   so important.  for all  ,  and   is multiplicative. (A function   is multiplicative if   for all  . ) How do we calculate   fast? Again, we can tweak the Eratosthenes's Sieve a little bit. void preprocess ( void ) { int i, j ; for ( i = 1 ; i <= 111100 ; i ++ ) { mu [ i ] = 1 ; primechk [ i ] = 1 ; } primechk [ 1 ] = 0 ; for ( i = 2 ; i <= 111100 ; i ++ ) { if ( primechk [ i ] == ...
Post a Comment
Read more

NT Part 5: Mobius Function Part 2. Mobius Inversion, Dirichlet Convolution

  Theorem.  Let   be arithmetic function such that  .  Then,  . Proof. using   for all   and  . The Dirichlet Convolution of two function   is the following. Denote   as the constant function,  .  is a function which satisfies   and   for  .  is the identity function,  The mobius inversion formula and the basic property of mobius functions give  ,  and  Okay. So what? How can we use this formula to  improve our lives  solve problems? We can, change our "sum" or our answer using mobius inversion and mobius functions to calculate them fast. I will give 3 examples which changes the desired sum by using number theory (like mobius function) to calculate them fast. Example Problems Problem 1.  http://www.spoj.com/problems/LCMSUM/ Let   be the answer when  . Precalculate  ,  and add   to every  . ...
Post a Comment
Read more