O(N) টাইম কমপ্লেক্সিটি

O(N) টাইম কমপ্লেক্সিটিকে বলা হয় লিনিয়ার টাইম কমপ্লেক্সিটি । ইনপুটের সাপেক্ষে আমাদের প্রোগ্রামের অপারেশন যদি সমান ভাবে বাড়তে থাকে তবে সেই কমপ্লেক্সিটি কে আমরা বলতেছি লিনিয়ার টাইম কমপ্লেক্সিটি বা O(N) টাইম কমপ্লেক্সিটি। আরেকটু ক্লিয়ার করে বললে , আমার প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভ্যরিয়েবল ইনপুট N এর উপর নির্ভর করে অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি ১০ বার সম্পাদন হয় , N এর ভ্যালু ১০০ হলে কাজটি ১০০ বার সম্পাদন হয় , N এর ভ্যালু ১০০০ হলে কাজটি ১০০০ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি , আমাদের কোডটির টাইম কমপ্লেক্সিটি O(N). চলুন ,কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বুঝার চেষ্টা করি । Problem 1 :

    int n ; cin >> n ;

    for(int i =0 ;i<n ;i++){
        cout << i << endl ;
    } 
    Input : 10
    Output : - 1 2 3 4 5 6 7 8 9 

উপরোক্ত কোডে নিচের for লুপটি ঠিক কতবার চলবে আমরা তা প্রোগ্রাম এ ইনপুট দেয়ার আগে বলে দিতে পারবো না। এখানে লুপটি কতবার চলবে , এবং এর মধ্যে দেয়া প্রিন্ট ইন্সট্রাকশন টি কতবার সম্পাদন হবে তা সম্পূর্ণ নির্ভর করছে একটি ভ্যারিয়েবল N এর উপর। N এর সুতারাং এই কোডের টাইম কমপ্লেক্সিটি হবে O(N) . Problem 2 :

    int n ; cin >> n ;

    for(int i =0 ;i<n ;i+=2){
        cout << i << " " ;
    } 
    Input : 10 
    Output : 0 2 4 6 8 10 

এই প্রবলেমের জন্য যদি আমরা N এর ভ্যালু ১০ ধরে নিই , তবে প্রথমে লুপটি তে i এর মান শুরু হবে ০ হতে। এরপরের স্টেপ এ i এর মান হয়ে যাবে 2 ,এরপর 4 , এরপর 6 , এরপর 8 এবং এর পরের স্টেপ এ i এর মান ১০ হয়ে যাবে এবং কন্ডিশন মিথ্যা হয়ে যাওয়ার কারণে লুপ টি ব্রেক করবে। আমরা যদি একটু খেয়াল করে দেখি সর্বমোট ৫ বার লুপের ভিতরের কাজটি সম্পাদন হয়েছে , যা আসলে ১০ এর অর্ধেক। যদি N এর ভ্যালু হতো ১০০ তবে কাজটি সম্পাদন হতো ১০০ এর অর্ধেক অর্থাৎ ৫০ বার । তার মানে আমরা বলতে পারি এই কোডের টাইম কমপ্লেক্সিটি হবে O(N/2). কিন্তু আমরা পূর্বের মডিউলে দেখে এসেছি , টাইম কমপ্লেক্সিটি নির্ণয়ের সময় আমরা সর্বদা ধ্রুব যে অংশটুকু আছে তা বাদ দিয়ে দিবো। সুতারাং এই কোডের টাইম কমপ্লেক্সিটি হবে O(N). Problem 3 (Reversing an Array) :

    for(int i =0 ;i<n/2 ;i++){
        int temp = a[i] ;
        a[i] = a[n-i-1] ;
        a[n-i-1] = a[i] ;
    }

উপরের কোড দ্বারা আমরা একটি N সাইজের এরে কে রিভার্স করতে পারি । এখানে যদি খেয়াল করে দেখি , এরে এর সাইজ যত হবে লুপটি তার অর্ধেক পরিমান চলবে । এবং সাথে সাথে এরেটি রিভার্স হয়ে যাবে। যেহেতু N এর অর্ধেক পরিমান ইন্সট্রাকশন এখানে সম্পাদন হচ্ছে , তাই Problem 2 এর মতো এই কোডের ও টাইম কমপ্লেক্সিটি হবে O(N). Problem 4 :

    // loop 1 :
    for(int i =1 ;i<=N ;i++){
        cout << i << " " ;
    }
    cout << endl ;
    
    //loop 2 :
    for(int j =1 ;j<=M ;j++){
        cout << j << " " ;
    }
    Input : 10 5  
    Output : 1 2 3 4 5 6 7 8 9 10
             1 2 3 4 5

উপরের কোডে প্রথম লুপটি মোট N বার চলবে এবং তা শেষ হলে দ্বিতীয় লুপটি মোট M বার চলবে । ধরি , N এর মান ১০ , এখন উপরের লুপটি ১০ বার চলবে, এরপর ধরি , M এর মান ৫ , এখন দুই নাম্বার লুপটি ৫ বার চলবে । সুতারাং পুরো প্রোগ্রাম এ সর্বমোট ১০+৫ = ১৫ টি কাজ সম্পাদন হচ্ছে। এখানে লক্ষ্য করে দেখা যায় , যদি আমরা পুরা কোড বিবেচনা করি তবে সর্বমোট আসলে কতটি কাজ সম্পাদন হচ্ছে তা হচ্ছে N এবং M এর যোগফলের সমান। সুতারাং এই কোডের টাইম কমপ্লেক্সিটি হলো O(N+M).

সহজে মনে রাখার উপায়ঃ আমার প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভ্যরিয়েবল ইনপুট N এর উপর নির্ভর করে অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি ১০ বার সম্পাদন হয় , N এর ভ্যালু ১০০ হলে কাজটি ১০০ বার সম্পাদন হয় , N এর ভ্যালু ১০০০ হলে কাজটি ১০০০ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি , আমাদের কোডটির টাইম কমপ্লেক্সিটি O(N).