কম Time complexity তে একটি সংখ্যার Divisor বের করার অ্যালগরিদম (Algorithm)

ডিভিসর কি আমরা সবাই হইতবা জানি । তবুও একটু আলোচনা করে নেওয়া যাক । ধরি একটি সংখ্যা ২০, তাহলে এর ডিভিসর হবে ১,২,৪,৫ এবং ২০ । কারন এই সব সংখ্যা দ্বারা ২০ কে ভাগ করা যাবে।তাহলে ডিভিসর কি সেইটা আমরা একটু ঝালিয়া নিলাম।এখন তাহলে এইটার প্রোগ্রাম নিয়ে আলোচনা করি।
আমরা সাধারনত ডিভিসর বের করার জন্য একটি লুপ চালিয়া মোড করে বের করে ফেলি।কিন্তু এইভাবে করলে আমাদের প্রোগ্রাম এর Time complexity অনেক বেড়ে যাবে। কারন যদি আমাদের বলা হয় ১০০০০০০০০০ এর ডিভিসর বের করতে দেন আমরা যদি সাধারণ ভাবে করি তাহলে আমাদের ১০০০০০০০০০ বার লুপ ঘুরাইতে হবে।এইটা আমাদের কাছে সহজ হলেও কম্পিউটার এর কাছে তা না।নিচে প্রোগ্রামটি এবং execution time দেখি।




তাহলে এখানে execution time ৭ সেকেন্ড। তাহলে আমাদের অউটপুট পেতে সময় লাগবে ৭ সেকেন্ড।যদি আরও বড় ইনপুট দেওয়া হত তাহলে অউটপুট আসতে আরও সময় লাগত। এই প্রোগ্রাম টিকেই আমরা আপডেট করে Time complexity কমিয়ে আনতে পারি। নিচের প্রোগ্রামটা দেখি।



এখানে কয়েকটা লাইন বেশী ইমপ্লেমেনট করা হয়েছে। এখন দেখি এখানে কি কি করা হয়েছে।এখানে লুপ এর মধ্যে sqrt ইউস করে আমরা লুপটা ঘুরানো কমাইছি। ১০০০০০০০০০ কে রুট করলে আমরা 31622 পাই। এখন আমাদের লুপ টা 31622 বার চলবে। আগের প্রোগ্রাম এ লুপ ১০০০০০০০০০ বার চালাইছিলাম। তাহলে পার্থক্য টা কিসুটা হলেও বুঝতে পারছি। তারপর পরের লাইন এ আমরা একটা কন্ডিশন ইউস করছি । এখানে বলা হয়েছে যদি value কে i দিয়ে মড করে ০ আসে তখন কন্ডিশন এর মধ্যে execution শুরু হবে অন্যথাই কন্ডিশন থেকে বের হয়ে যাবে। দেন আরেকটি কন্ডিশন ইউস করা হইছে যদি value কে i দিয়ে ভাগ করে ভাগফল  i হয় দেন একটি সংখ্যা প্রিন্ট করবে। অন্যথাই ২ টি সংখ্যা প্রিন্ট করবে। একটি  i অপর টি  value/i । নিচে if এবং else  কন্ডিশন  আলোচনা করা হল।

else
ধরি value=100
Value_sqrt=10;
দেন এই লুপটি এখানে ১০ বার চলবে। ১০ বার লুপ ঘুরিয়ে আমরা ডিভিসর পাব ১,২,৫,১০। এগুলা i এর ভ্যালু।যদি আমরা i এর ভ্যালু কে value দিয়ে ভাগ করি দেন আমরা "Value_sqrt" এর পরের ডিভিসর গুলা পাব। যেমন ১০০/১=১০০,১০০/২=৫০,১০০/৫=২০।এগুলো value/i এর ভ্যালু।

if
else কন্ডিশন এ আমি ১০০/১০ করিনি।কারন ১০ কে আমি  "Value_sqrt" এর আগেই পেয়ে গেছি।যদি আমি ভাগ করি দেন ১০ ই পাব।কারন ১০০/১০=১০। এর কারনেই এখানে if কন্ডিশন এর মধ্যে বলা হয়েছে যদি value/i == i দেন প্রিন্ট i ।

বি দ্রঃ ভুল ত্রুটি মার্জনীয়।