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

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

    int n ; cin >> n ;
    
    for(int i =N ;i>1 ;i= i/2 ){
    cout << i << endl ;
    }
    
    Input : 100 
    Output : 100 50 25 12 6 3 

চলেন , উপরের কোডে লুপ টি কয়বার চলবে তা আমরা একটি উদাহরণের সাহায্যে দেখার চেষ্টা করি। ধরেন , N এর মান ১০০। প্রথমে লুপ ১০০ (১ নং) থেকে শুরু হবে , এরপর ১০০/২ = ৫০ (২ নং) -> ৫০/২ = ২৫ (৩ নং) -> ২৫/২ = ১২ (৪ নং) -> ১২/২ = ৬ (৫ নং) -> ৬/২ = ৩ (৬ নং) -> ৩/২ = ১ , এখানে লুপ টি থেমে যাবে। দেখা যাচ্ছে এখানে সর্বমোট ৬ বার লুপ টি চলেছে। দেখা যাচ্ছে ১০০ কে ২ দিয়ে যতবার ভাগ করা যাচ্ছে ঠিক তত সংখ্যক বার লুপটি চলছে। আর একটি সংখ্যা N কে ২ দিয়ে কতবার ভাগ করা যাবে তা আমরা প্রকাশ করি logN দ্বারা। তাই এই কোডের টাইম কমপ্লেক্সিটি হলো O(logN). Problem 2 :

    int n ; cin >> n ;

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

    Input : 100 
    Output : 1 4 8 16 32 64

কিছু উদাহরণের সাহায্যে আমরা N এবং এই কোডের লুপ সংখ্যার সাথে তা বের করার চেষ্টা করবো। ধরেন N এর মান হলো ১০। এখন i =1 থেকে শুরু হবে , 1*2 = 2 (১ বার) -> 2*2-> 4 (২ বার) -> 4*2 -> 8 (৩ বার) , 8*2 = 16> 10 , লুপটি এখানে থেমে যাবে। সুতারাং সর্বমোট log10 ~3 বার এই লুপটি চলেছে । এরপর আসেন , N এর মান ১০০ এর জন্য টেস্ট করে দেখি বিষয় টি। i =1 , থেকে শুরু হবে এরপর 1*2 = 2 (১ বার) -> 2*2-> 4 (২ বার) -> 4*2 -> 8 (৩ বার) , 8*2 = 16 (4 বার) -> 16*2 -> 32 (৫ বার) -> 32*2 = 64 (৬ বার) -> 64*2=128>100 এখানে লুপটি থেমে যাবে। সুতারাং সর্বমোট log100 ~6 বার লুপটি চলেছে। সবশেষে এখান থেকে আমরা বুঝতে পারতেছি যে কোন একটি সংখ্যা কে ম্যাক্সিমাম কয়বার ২ দিয়ে গুণ করা যাবে যাতে করে তা N এর থেকে ছোট হয় / সমান হয় , তা হলো ঐ সংখ্যার লগের সমান অর্থাৎ logN এর সমান । তাই উপরের কোডের টাইম কমপ্লেক্সিটি হচ্ছে O(logN). Problem 3 :

    k=2 ;
    for(int i =0 ;i<n ;i++){
        i*=k ;
    }

উপরের কোড এ আমাদের মনে হতে পারে , লুপটি তে যেহেতু i এর মান ০ থেকে শুরু হয়ে N এর আগ পর্যন্ত যাচ্ছে এবং প্রত্যেক ক্ষেত্রে i++ হচ্ছে তাই হয়তো এর কমপ্লেক্সিটি O(N) এর সমান। কিন্তু ভিতরের ইন্সট্রাকশন এ লক্ষ্য করলে দেখা যায় , সেখানে i এর মানের সাথে প্রত্যেকবার 2 গুণ হচ্ছে। এবং উপরের প্রবলেম থেকে জেনে এসেছি , কোন একটি সংখ্যা কে ম্যাক্সিমাম কয়বার ২ দিয়ে গুণ করা যাবে যাতে করে তা N এর থেকে ছোট হয় / সমান হয় , তা হলো ঐ সংখ্যার লগের সমান অর্থাৎ logN এর সমান। তাই এই কোডের টাইম কমপ্লেক্সিটি হবে O(logN).

সহজে মনে রাখার উপায়ঃ যখন আমাদের কোডে কোন একটি লুপের key variable যেমন i এর মান যদি দিগুন হারে বাড়তে থাকে অথবা i এর মান প্রতিক্ষেত্রে অর্ধেক হয়ে কমতে থাকে , সেই ক্ষেত্রে আমরা বলতে পারি আমাদের কোডের টাইম কমপ্লেক্সিটি হলো O(logN)