Calculate Big O Time Complexity | টাইম কমপ্লেক্সিটি বের করা

কোনো এলগোরিদমের টাইম কমপ্লেক্সিটি বের করার সময় আমরা কিছু নিয়ম ফলো করি। যেমনঃ

১ । কন্সট্যান্ট পদ বাদ দেয়াঃ যদি কোনো কমপ্লেক্সিটি আসে O(3n+2)  তাহলে সেটা আসলে O(n)  লিখা যায়। কারণ Asymptotic Notation এর ক্ষেত্রে আমরা আমরা রিলাশনটা খুঁজি যে এটা লিনিয়ার নাকি লগারিদ্মিক ইত্যাদি আমরা একচুয়াল অপারেশন কত চলবে এইটা বের করি না। আর n এর খুব বড় মানের জন্য এদের তেমন কোনও ভূমিকা ও নেই। ধরি n এর মান ১, তাহলে O(3n+2)  = (৩*১+২) = ৫ কিন্তু n এর মান যদি ১লক্ষ হয় তাহলে রেসাল্ট এর সাথে ২ যোগ করা না করা কম্পিউটারের জন্য কিছুই না। সেম কথা ৩ গুনের জন্য প্রযোজ্য । n এর মান ১০ হলে ৩ গুণ ৩০ হবে, ২০ হলে ৬০ হবে, কিন্তু ৩ গুণ না হয়ে যদি n গুণ হত তাহলে কমপ্লেক্সিটি হতো O(n²) n=১০ হলে হত ১০০ আর ২০ হলে ৪০০ তখন কিন্তু আমরা আর একে বাদ দিতাম না, তাই কমপ্লেক্সিটি তে কন্সট্যান্ট পদ বাদ দেয়া হয় ।

২ । নন ডমিন্যান্ট পদ বাদ দেয়াঃ O(n² + n + 4) এমন হলে আমরা কন্সট্যান্ট বাদ দিব তাহলে হবে O(n² + n) এখন চিন্তা করে দেখি এখানে ডমিন্যান্ট পদ বা সবচেয়ে বড় পদ কিন্তু n² যদি এর মান হয় ১০, তাহলে এর ভ্যালু হবে ১০০+১০ যদি ১০০ হত তাহলে ১০০০০+১০০ আগের মত চিন্তা করলেই আমরা বুঝব যে ১০০০০ অপারেশন করার কম্পিউটার টাইমের তুলনায় কিন্তু ১০০ এর টাইম অনেক কম এভাবে এর মান আরো বড় হলে নন ডমিন্যান্ট পদ গুলোর ইফেক্ট থাকবে না।

৩ । মাল্টিপল লুপঃ নিচের কোড স্নিপেট দুইটা দেখি।

test_case = int(input())

for i in range(test_case):
    print(f'this will print {i} in first loop')

for j in range(test_case):
    print(f'this will print {j} in second loop')

যখন নেস্টেড লুপ হয়ঃ

test_case = int(input())

for i in range(test_case):
    print(f'this will print {i} in first loop')
    for j in range(test_case):
        print(f'this will print {j} in second loop')

• প্রথম ক্ষেত্রে দুইটা লুপ test_case পর্যন্ত চলতেছে। ফার্স্ট লুপের টাইম হবে O(test_case) আর দ্বিতীয়টার O(test_case)। তাহলে টোটাল হবে O(test_case + test_case)। এখানে যোগ হলো কেন? কারণ প্রথম লুপের কাজ শেষ হবার পর দ্বিতীয় লুপ চলতেছে। এমন ক্ষেত্রে কমপ্লেক্সিটি গুলো যোগ হয়।
• দ্বিতীয় ক্ষেত্রেও লুপ দুইটা, কিন্তু প্রথম লুপের প্রতিটা ইলিমেন্ট এর জন্য দ্বিতীয় লুপ সম্পুর্ন চলতেছে। এমন ক্ষেত্রে কমপ্লেক্সিটি গুলো গুণ হবে। তাহলে এর কমপ্লেক্সিটি হবে O(test_case * test_case)

৪ । লগারিদ্মিক কমপ্লেক্সিটিঃ প্রথমে আমরা চিন্তা করি লগ আসলে কি? আমার সবসময় এই লগ কে সংজ্ঞায়িত করতে কষ্ট হতো রিসেন্টলি আমি ইউটিউবে Eddie Woo এর একটা লেকচার দেখি সেটাই এখানে বলছি।

লগ হলো আসলে এক্সপোনেনশিয়াল কে অন্য ভাবে দেখার একটা উপায় ।

তাহলে এখন আমাদের দেখতে হবে এক্সপোনেনশিয়াল কিভাবে কাজ করে। আমরা জানি (Base^Exponent) এটা হলো এক্সপোনেনশিয়াল এর সূত্র এর মানে হলো বেজ কে বেজ দিয়েই এক্সপোনেন্ট বার গুণ করা। ২^৪ এটার মানে কিন্তু ২*২*২*২ = ১৬ , বেজ ২ আর এক্সপোনেন্ট ৪ সুতরাং ২ কে ২ দিয়েই ৪ বার গুণ করতে হবে।
মনে করি আমাদের একটা জাদুর লাঠি আছে যার ইনিশিয়াল সাইজ ১ মিটার কিন্তু এর সাইজ প্রতি ইউনিট টাইমে ডাবল হয়ে যায় ! তাহলে

• ০ সেকেন্ডে সাইজ = ১ মিটার = ২^০
• ১ সেকেন্ডে সাইজ = (আগের স্টেপের সাইজ) ১*২ মিটার = ২ মিটার = ২^১
• ২ সেকেন্ডে সাইজ = ২*২ মিটার = ৪ মিটার = ২^২
• ৩ সেকেন্ডে সাইজ = ৪*২ মিটার = ৮ মিটার = ২^৩
• ৪ সেকেন্ডে সাইজ = ৮*২ মিটার = ১৬ মিটার = ২^৪

আমরা দেখতে পারি এই বেজটা আসলে ইলিমেন্ট এর গ্রোথ রেট বোঝায় ০ সেকেন্ডে এর কোনও গ্রোথ নেই আগের যা সাইজ ছিল তাই ১ মিটার। ১ সেকেন্ডে সে ডাবল হয়ে যাচ্ছে , ২ সেকেন্ডে ৪ গুণ । সো আমরা সূত্রটা এভাবে লিখতে পারি (Growth Rate ^Times) = Final Result । তার মানে আমার প্রোডাক্ট এর গ্রোথরেট যদি ২ হয় তাহলে ৫ সেকেন্ড পরে এর ফাইনাল সাইজ কত হবে? => ২^৫=৩২ অর্থাৎ আমরা এক্সপোনেনশিয়াল দিয়ে ফাইনাল রেজাল্ট বের করি। এখন যদি এমন হয় যে আমরা ফাইনাল রেসাল্ট জানি আর গ্রোথরেট জানি কিন্তু টাইম জানি না তখন আমরা টাইম কিভাবে বের করব ?
যদি আমরা ফাইনাল রেসাল্ট কে গ্রোথ দিয়ে ভাগ করতে থাকি তাহলে যতবার ভাগ করে আমরা উত্তর ১ পাব সেটাই কিন্তু টাইম। আর এটাই আসলে লগ আর এক্সপোনেনশিয়াল এর সম্পর্ক। একটা অন্যটার ইনভার্স বা বিপরীত।

• > (গ্রোথরেট ^সময় ) = রেসাল্ট হলে <=> Log_{গ্রোথরেট} রেসাল্ট = সময়
• base^power = N <=> Log_baseN = power

এখন আমাদের কমপ্লেক্সিটি এর সময় যদি আমরা দেখি আমাদের ইনপুট সাইজ প্রতি স্টেপে নির্দিষ্ট হারে কমে যাচ্ছে তাহলে আমরা বুঝতে পারবো যে এর কমপ্লেক্সিটি হবে লগারিদ্মিক।

যেমন বাইনারি সার্চ এর ক্ষেত্রে আমরা জানি যে প্রতিবার আমরা এরের মিড ভ্যালু এর সাথে তুলনা করি আর ছোট হলে ডান পাশের এলিমেন্টস নিয়ে নতুন অ্যারে আর বড় হলে বাম পাশেরগুলো নিয়ে নতুন এরে বানাই। তাহলে প্রতিবার কিন্তু আমাদের ইনপুট সাইজ অর্ধেক করে কমে যাচ্ছে। এমন প্রতিবার অর্ধেক করে কমে গেলে সেগুলা বেশিরভাগ ক্ষেত্রেই O(logN) কমপ্লেক্সিটি হয়।

৫। রিকার্সিভ ফাংশনঃ আমরা একটা ফাংশন দেখি

def recursive(n):
    if n<=1:
        return 1
    return recursive(n-1) + recursive(n-1)
    
print(recursive(5))

এই ফাংশনের কমপ্লেক্সিটি কত? এমন রিকার্সিভ ফাংশনের ক্ষেত্রে আমরা দেখব ১। প্রতিটা ফাংশন কলে এর কয়টা বার্ঞ্চ হচ্ছে। আমরা দেখি এই ফাংশনটা দুইটা করে কল করছে । ৫ পাঠালে সে দুইবার ৪ এর জন্য কল করবে, প্রতিটা ৪ এর জন্য দুইবার করে ৩ এভাবে কল করতেই থাকবে বেস কেস পর্যন্ত। তাহলে দেখি টোটাল কলগুলো কেমন হবে

[৫ > ৪ ৪ > ৩ ৩ ৩ ৩ > ২ ২ ২ ২ ২ ২ ২ ২ > ১ ১ ১ ১ ১ ১ ১ ১ ১ ১ ১ ১ ১ ১ ১ ১ ]

এর ব্রাঞ্চ হচ্ছে দুইটা করে আর এর ডেপ্তথ হলো ৫ ( বেস কেস পর্যন্ত যে কয়টা স্টেপ/ লেভেল) । সাধারণত রিকার্সিভ সল্যুশন এর ক্ষেত্রে (বেশির ভাগ সময়) কমপ্লেক্সিটি হয় ( ব্রাঞ্চ^ডেপথ ) = এক্ষেত্রে তাহলে উত্তর হবে ২^৫ মানে 2^N বা এক্সপোনেনশিয়াল কমপ্লেক্সিটি ।

লিখাটি পড়ার জন্য আপনাকে ধন্যবাদ। লিখায় কোনো ভুল থাকলে আমাকে জানিয়ে সাহায্য করবেন। এর পরে আমরা হয়তো ভিডিও পোস্ট করতে পারি, ইউটিউব এ সাবস্ক্রাইব করে রাখতে পারেন।