আপডেট
Showing posts with label অ্যালগোরিদম. Show all posts
Showing posts with label অ্যালগোরিদম. Show all posts

Wednesday, October 14, 2015

অ্যালগোরিদম কমপ্লেক্সিটি (বিগ “O”)


প্রবলেম সলভ এর এক একটি পদ্ধতি হলো এক একটি অ্যালগোরিদম। এখন কথা হচ্ছে একটি প্রব্লেম অনেক উপায়ে সল্ভ করা যায়।  অর্থাৎ অ্যালগোরিদম ও অনেক থাকতে পারে , সেক্ষেত্রে যে অ্যালগোরদমটি বেশী কার্যকরী সেটি ই বেছে নিব। কোন অ্যালগোরিদম ভালো তা বোঝার জন্য দেখতে হবে -আমি যে অ্যাালগোরিদম টি করব সেটি বড় ইনপুট এর জন্য কাজ করবে কিনা , আউটপুট পেতে কত সময় লাগবে , মেমোরি কতটুকু ব্যবহা্র  হচ্ছে । অ্যালগোরিদম এর কমপ্লেজিটি বের করে এই প্রশ্ন গুলোর উত্ত্রর পাওয়া যাবে।কমপ্লেজিটি বলতে মুলত  অ্যালগোরিদমের ধাপ এর উপর ভিত্তি করে বের করা হয়।  যেমনঃ

উপরের কোডটিতে n এর মান যাই হোক না কেন একটি মাত্র  constant ধাপ এর পর অ্যালগরদমটি কাজ করা শেষ করবে । তাই এর কমপ্লেজিটি O(1)।   BIG “O” নোটেশন হলো কমপ্লেক্সিটি লিখে প্রকাশ করার নোটেশন।
আবার এক্ষেত্রে কোডটিতে একটি লুপ আছে । লুপটি কত ধাপ চলবে তা n এর মানের উপর নির্ভর করে । n=5 হলে এটি পাঁচটি ধাপে চলবে বা n=10 হলে দশটি ধাপে চলবে । যেহেতু n এর মানের উপর নির্ভর করছে তাই এর কমপ্লেজিটি O(n)

লিনিয়ার সার্চঃ
লিনিয়ার সার্চ এর ক্ষেত্রে for লুপ দিয়ে সংখ্যা মান সার্চ করছি । যদি লিস্ট এর প্রথমেই সংখ্যাটি থাকে তখন লুপটি মাত্র এক বা্র চলবে। সেক্ষেত্রে এটি হবে best case. আর যদি সংখ্যাটি  লিস্ট এর সর্বশেষে থাকে বা লিস্টে না থাকে তখন লুপটি n সংখ্যকবার চলবে (worst case )। কমপ্লেজিটি এর ক্ষেত্রে প্রোগ্রামাররা সব সময় worst case নিয়ে কাজ করে। সুতরাং লিনিয়ার সার্চ এর কমপ্লেজিটি O(n).
বাইনা্রি সার্চঃ
  বাইনা্রি সার্চ এর ক্ষেত্রে প্রতিবার লিস্টকে দুইভাগে ভাগ করে , এর এক অংশ বা্দ দিয়ে দেই । এভাবে সার্চকৃত সংখ্যা না পাওয়া পর্যন্ত চলতে থাকে । এখন একটি সংখ্যাকে সর্বোচ্চ কত বার দুই দিয়ে ভাগ করা যায় যতক্ষন না পর্যন্ত ১ না হয় ? দেখা যাক ...
অর্থাৎ বাইনারি সার্চে সর্বোচ্চ log2(n) সংখ্যক ধাপের পর আমরা দরকারি সংখ্যাটা খুজে পাবো, সুতরাং এর কমপ্লেজিটি  O(log2(n))

বাবল সর্ট এলগরিদম

বাবল সর্টের মুল ব্যাপারটা হল প্রতিটি এলিমেন্টকে তার নিকটতম এলিমেন্টের সাথে তুলনা করতে হবে। যদি পূর্বেকার এলিমেন্ট বড় হয় তাহলে তাদের মধ্যে সোয়াপ করতে হবে, নাহলে কিছুই করতে হবেনা। আর এভাবে 1----- N পর্যন্ত চলতে থাকবে।
যেমন নিচের ৮ সংখ্যার ক্ষেত্রে যদি তা করিঃ 
৬,৫,৩,১,৮,৫,২,৪
------------
৫,৬,৩,১,৮,৫,২,৪
৫,৩,৬,১,৮,৫,২,৪
৫,৩,১,৬,৮,৫,২,৪
৫,৩,১,৬,৮,৫,২,৪
৫,৩,১,৬,৫,৮,২,৪
৫,৩,১,৬,৫,২,৮,৪
৫,৩,১,৬,৫,২,৪,৮ 

প্রথমে ০ এবং ১ নাম্বার ইনডেক্সকে তুলনা করেছি, তারপর ১,২ নাম্বার এভাবে ৭ এবং ৮ নাম্বার পর্যন্ত তুলনা করছি এবং অদল বদল করছি। পুরো এই কাজটা আমাকে করতে হচ্ছে ৭ বারে। এখানে আসলে নিন্মোক্ত ইন্ডেক্সগুলো আমি পর পর তুলনা করছি।
০,১
১,২
২,৩
৩,৪
৪,৫
৫,৬
৬,৭
৭,৮
বুঝতে সমস্যা হলে এই ছবিটি দেখা যেতে পারে- 
বাবল সর্ট সিমুলেশন
এখন এটি যদি প্রোগ্রামিং এর সাহায্যে করি তাহলে কিভাবে করতে হবে?
আমাকে শুন্য থেকে শুরু করে (N-1) পর্যন্ত লুপ চালাতে হবে। কারন (N-1)  ইনডেক্সে  গেলেই আমি N  কে পেয়ে যাচ্ছি। উপরের কাজটির জন্য লুপটি লিখে ফেলি তাহলেঃ 
 For(i= 0;i<n-1;i++){  
      If(num[i]>num[i+1]){  
           Int temp= num[i];  
           num[i]= num[i+1];  
           num[i+1]= temp;  
 }  
 }
খেয়াল করলে দেখতে পারবে উপরে আমি যে সিমুলেশন দেখাইলাম তাতে নাম্বারগুলো পুরোপুরি সর্ট হয়নাই। উপরের সে কাজটা আমাকে আরো কয়েকবার করতে হবে তারপর কোন এক সময় পুরো নাম্বারগুলো সর্ট হবে।
মানে, উপরের ঐ কাজটাকে আমাকে আরো কয়েকবার করতে হবে। সর্বোচ্চ N-1  বার করলে আমার নাম্বারটা পুরোপুরি সর্ট হবে। তাহলে উপরের অ্যারেটির জন্য আমাকে কাজ করতে হচ্ছে, ৭ বার।

তাহলে আমাদের উপরের লুপকে আরো (N-1) বার ঘুরালেই হয়ে যাবে। মানে আমরা ঐ লুপকে আরেকটি লুপের আন্ডারে ফেলে দিলেই কাজ শেষ। 


 For(j=0;j<n-1;j++){  
 For(i= 0;i<n-1;i++){  
      If(Num[i]>num[i+1]){  
           Int temp= num[i];  
           Num[i]= num[i+1];  
           Num[i+1]= temp;  
 }  
 }  
 }
দ্বিতীয় স্টেপে এরকম হবেঃ  


৩,৫,১,৬,৫,২,৪,৮

৩,১,৫,৬,৫,২,৪,৮

৩,১,৫,৬,৫,২,৪,৮

৩,১,৫,৫,৬,২,৪,৮

৩,১,৫,৫,২,৬,৪,৮
৩,১,৫,৫,২,৪,৬,৮
৩,১,৫,৫,২,৪,৬,৮

তৃতীয় স্টেপঃ  

১,৩,৫,৫,২,৪,৬,৮
১,৩,৫,৫,২,৪,৬,৮
১,৩,৫,৫,২,৪,৬,৮
১,৩,৫,২,৫,৪,৬,৮
১,৩,৫,২,৪,৫,৬,৮
১,৩,৫,২,৪,৫,৬,৮
১,৩,৫,২,৪,৫,৬,৮

-----------
-----------
N-1   স্টেপ  শেষেঃ   
১,২,৩,৪,৫,৬,৭,৮ 

টাইম কমপ্লেক্সিটিঃ
উপরের j= 0 এর জন্য I, (N-1) বার ঘুরবে
J=1 এর জন্য I, (N-1) বার ঘুরবে
----------------------
----------------------
J= (N-1) এর জন্য I , (N-1) বার ঘুরবে

তাহলে  মোট ঘুরবে
(N-1)*(N-1)
N^2-N-N+1
N^2-2N+1

বিগ ও হিসেবে টাইম কমপ্লেক্সিটি হবে N^2
O(N^2) 


Friday, October 9, 2015

অ্যালগোরিদম এর বাংলা টিউটোরিয়াল ( Merge Sort )

অ্যালগোরিদম এর বাংলা টিউটোরিয়াল ( Merge Sort )



video:





Source code

Wednesday, October 7, 2015

অ্যালগোরিদম এর বাংলা টিউটোরিয়াল ( Boubble Sort )

অ্যালগোরিদম এর বাংলা টিউটোরিয়াল ( Boubble Sort )



Tuesday, October 6, 2015

অ্যালগোরিদম এর বাংলা টিউটোরিয়াল ( Insertion Sort )


অ্যালগোরিদম এর বাংলা টিউটোরিয়াল ( Insertion Sort )''


Sunday, October 4, 2015

অ্যালগোরিদম এর বাংলা টিউটোরিয়াল ( লিনিয়ার এবং বাইনারি সার্চ )

                           অ্যালগোরিদম এর বাংলা টিউটোরিয়াল 



লিনিয়ার সার্চ:






বাইনারি সার্চ:







ভিডিও টি ভালো লাগলে আমার চ্যানেলে subscribe করুন 
Source:



  #tags:

   algorithm bangla tutorial
 Algorithm Bangla tutorials - linear search
 Algorithm  tutorials in bangla  - bainary search

  Bangla tutorials

 Algorithm  tutorials in bangla  - linear search in c 





Subscribe to: Posts ( Atom )