ধরা যাক Algorithm A এর running time O(n²) এবং Algorithm B এর running time O(n)। তাহলে নিচের কোনটি সবচেয়ে সঠিক?
সঠিক উত্তর
গAlgorithm A, Algorithm B এর চেয়ে asymptotically ধীর গতির
ব্যাখ্যা
প্রশ্নটি বিগ ও নোটেশন বোঝা যাচাই করছে। বিগ ও বলে ইনপুটের আকার বড় হতে থাকলে চলার সময় কোন হারে বাড়ে; একে বলে অ্যাসিম্পটোটিক আচরণ। এটি ছোট ইনপুটের আসল গতির নিশ্চয়তা দেয় না।
অ্যালগরিদম এ-র সময় বাড়ে এন বর্গের হারে, বি-র সময় এন-এর হারে। এন দশ গুণ হলে বি-র সময় দশ গুণ হয়, কিন্তু এ-র সময় একশো গুণ। তাই এন যথেষ্ট বড় হলে এ অবশ্যই বি-এর চেয়ে ধীর।
কিন্তু বিগ ও ধ্রুবক গুণক বাদ দিয়ে লেখা হয়। ধরুন এ আসলে নেয় এন বর্গ ধাপ, আর বি নেয় একশো গুণ এন ধাপ। তাহলে এন দশ হলে এ-র লাগে একশো ধাপ, বি-র এক হাজার; অর্থাৎ ছোট ইনপুটে এ-ই দ্রুত। এন এক হাজার হলে এ-র লাগে দশ লাখ ধাপ, বি-র মাত্র এক লাখ।
তাই সবচেয়ে নিখুঁত কথা হলো এ, বি-এর চেয়ে অ্যাসিম্পটোটিক্যালি ধীর। ফাঁদ হলো প্রথম আর শেষ বিকল্প; এগুলো সব ইনপুটের জন্য সত্য বলে দাবি করে, যা বিগ ও দিয়ে প্রমাণ হয় না।
- ধরি A = n² ধাপ, B = ১০০n ধাপ
- n = ১০: A = ১০০, B = ১,০০০ → A দ্রুত
- n = ১০০: A = ১০,০০০, B = ১০,০০০ → সমান
- n = ১,০০০: A = ১০,০০,০০০, B = ১,০০,০০০ → B দ্রুত
- বড় n-এ সবসময় A ধীর → A asymptotically ধীর
স্টেপ বাই স্টেপ শিখুন
৪/৪- বিগ ও ধ্রুবক বাদ দেয়; ধরি A নেয় n² ধাপ, B নেয় ১০০n ধাপ।
- n = ১০ হলে A-র লাগে ১০০, B-র ১,০০০ ধাপ: ছোট ইনপুটে A দ্রুত।
- n = ১০০ হলে দুটোরই ১০,০০০ ধাপ: এখানে সমান।
- n = ১,০০০ হলে A-র ১০ লাখ, B-র ১ লাখ ধাপ: বড় ইনপুটে A ধীর, তাই asymptotically ধীর।
ক. Algorithm A, Algorithm B এর চেয়ে ধীর গতির: শর্তহীনভাবে ধীর বলা যায় না; ছোট n-এ ধ্রুবক গুণকের কারণে A দ্রুতও হতে পারে।
খ. Algorithm A, Algorithm B এর চেয়ে দ্রুত গতির: উল্টো দাবি; বড় n-এ n² সবসময় n-কে ছাড়িয়ে যায়, তাই A সাধারণভাবে দ্রুত হতে পারে না।
ঘ. Algorithm B সর্বদা Algorithm A এর চেয়ে দ্রুত চলে: ‘সর্বদা’ ভুল; যেমন A = n² আর B = ১০০n হলে n < ১০০ পর্যন্ত A-ই দ্রুত।
Big-O প্রশ্নে ‘সর্বদা’ বা শর্তহীন ‘দ্রুত/ধীর’ লেখা বিকল্প সাধারণত ভুল; ‘asymptotically’ শব্দটি খুঁজুন।
বিগ ও বলে বড় ইনপুটের গল্প, ছোট ইনপুটের নয়।