অ্যাসিমটোটিক নোটেশন (Asymptotic Notation)

ধরা যাক, আমরা অনেক বড় কিছু সংখ্যার যোগ করব, তাহলে এই অপারেশনে কত সময় লাগবে? প্রথমেই যে প্রশ্ন আসবে সেটা হচ্ছে কতগুলো সংখ্যা, আচ্ছা ধরে নিলাম সেই সংখ্যাটা n. এই সময়টা কি আমরা নির্দিষ্ট করে বলতে পারি? হ্যা, সেটা বলা যায় একটা নির্দিষ্ট একটা কম্পিউটারের জন্য। সার্বজনীনভাবে কখনোই বলা যাবেনা। কারণ কম্পিউটেশন পাওয়ার অনেকাংশে নির্ভর করে কম্পিউটারের প্রসেসর ও মেমরির[efn_note]এখানে মেমরি বলতে প্রাইমারি মেমরি বোঝানো হয়েছে।[/efn_note] উপরে। একটা সেলেরন প্রসেসর যে কাজ করতে পারবে তার চেয়ে কোর আই-৭ এর প্রসেসিং ক্ষমতা অনেক বেশি হবে এটা স্বাভাবিক।

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

এই সমস্যা সমাধানের জন্য অ্যালগরিদমের কমপ্লেক্সিটি অ্যাসিমটোটিক নোটেশনে প্রকাশ করা হয়। ইনপুট সাইজের উপর ভিত্তি করে রানটাইমে কি ধরনের কমপ্লেক্সিটি আসবে সেটা অ্যাসিমটোটিক নোটেশনের মাধ্যমে নির্ণয় করা হয়। সাধারণত[efn_note]little-O বা little-Θ তেও প্রকাশ করা যায়।[/efn_note] তিন ধরনের নোটেশনের মাধ্যমে আমরা কোন অ্যালগরিদমের কমপ্লেক্সিটি পরিমাপ করতে পারি –

বিগ-ও (Big-O)

Big-O হচ্ছে একটা অ্যালগরিদম রান করতে সর্বোচ্চ কত সময় লাগবে (worst case) তার পরিমাপ, অর্থাৎ অ্যালগিরদমের আপার বাউন্ড (upper bound) এই নোটেশনের মাধ্যমে প্রকাশ করা হয়।

f(n) = O(g(n)) (read as “f of n is big oh of g of n”) iff (if and only if) there exist positive constants c and n0 such that f(n)≤cg(n) for all n,

example, 3n+2=O(n) as 3n+2≤4n for all n≥2

as for all n≥5

g(n) is upperbound on the value of f(n) for all n, n≥n0

Theory:

If then

বিগ-ওমেগা(Big-Ω)

Big-Ω হচ্ছে একটা অ্যালগরিদম রান করতে সর্বনিম্ন কত সময় লাগবে (best case) তার পরিমাপ, অর্থাৎ অ্যালগিরদমের লোয়ার বাউন্ড (lower bound) এই নোটেশনের মাধ্যমে প্রকাশ করা হয়।

f(n) = Ω(g(n)) (read as “f of n is omega of g of n”) iff there exist positive constants c and n0 such that f(n)≥cg(n) for all n, n≥n0

example, 3n+2=Ω(n) as 3n+2≥3n for all n≥1

as for all n≥1

g(n) is only a lower bound on f(n)

Theory:

If then

বিগ-থিটা(Big-Θ)

Big-Θ হচ্ছে একটা অ্যালগরিদম রান করতে সর্বোচ্চ বা সর্বনিম্ন যে সময় লাগবে তার গড় হিসাব।

f(n) = Θ(g(n)) (read as “f of n is theta of g of n”) iff there exist positive constants c1, c2, and n0 such that c1g(n)≤f(n)≤c2g(n) for all n, n≥n0

example, 3n+2=Θ(n) as 3n+2≥3n for all n≥2 and 3n+2≤4n for all n≥2, so

             c1=3, c2=4, and n0=2

g(n) is both an upper and lower bound on f(n)

Theory:

If then

উপরের চিত্রটিতে এই তিন ধরনের নোটেশনের একটা তুলনামূলক চিত্র অঙ্কণ করা হয়েছে।