কম্পিউটার বিজ্ঞানের ভিত্তি/অ্যালগরিদমের জটিলতা
অ্যালগরিদম জটিলতা
সম্পাদনা"অ্যালগরিদম হল একটি বিমূর্ত ধারণা, এটি একটি প্রক্রিয়া নির্ধারণ করে যা একজন মানুষ, কম্পিউটার বা অন্য উপায়ে সম্পন্ন হতে পারে। এইভাবে এটি অসংখ্য প্রয়োগ সহ একটি খুব সাধারণ ধারণার প্রতিনিধিত্ব করে"- ডেভিড হারেল, "অ্যালগরিদমিক্স-দ্য স্পিরিট অফ কম্পিউটিং"।
আমরা শিখেছি যে অ্যালগরিদম সমস্যার ধারণাগত সমাধান। গণ্না অ্যালগরিদমগুলি্র কাজের সাধারণ ইউনিটগুলির পরিপ্রেক্ষিতে বর্ণনা/সংজ্ঞায়িত হিসেবে বর্ণ্না করা যেতে পারে যা কম্পিউটারগুলি করতে পারে যাতে তারা প্রোগ্রামিং ভাষা এবং কার্যকর পরিবেশের জন্য নিরপেক্ষ হয়। (কম্পিউটারস) অ্যালগরিদম লেখা এমন একটি সৃজনশীল প্রক্রিয়া যেমন ফ্রান্সিস সুলিভান উল্লেখ করেছেন যে "আমার কাছে, দুর্দান্ত অ্যালগরিদমগুলিগ গণ্না্র কবিতা। পদ্যের মতো এগুলিও সংক্ষিপ্ত, লোভনীয়, ঘন এবং এমনকি রহস্যময় হতে পারে। কিন্তু একবার বিকশিত হয়ে গেলে, তারা গ্ণনা্র কিছু দিকের উপর একটি উজ্জ্বল নতুন আলো ফেলে। আপনি সিউডো কোড এবং ফ্লোচার্টের মতো বিমূর্ত স্বরলিপি ব্যবহার করে নথিভুক্ত উদাহরণ অ্যালগরিদমগুলি দেখেছেন।
যখন একবার অ্যালগরিদম প্রয়োগ/কোড করা হয়, যেমনঃ বিমূর্ত প্রতীক দ্বারা প্রতিনিধিত্ব করে, তারা প্রোগ্রামে জীবন্ত হয়ে ওঠে যা তাদের মূর্ত করে। প্রোগ্রামগুলি কম্পিউটার দ্বারা এক্সিকিউটেবল/রানযোগ্য। সমস্ত ধরনের অ্যালগরিদম প্রয়োগ করে এমন বিভিন্ন প্রোগ্রাম চালানোর ক্ষমতা মেশিন হিসাবে কম্পিউটারের একটি অনন্য বৈশিষ্ট্য। সাধারণত যখন আমরা একটি মেশিন কিনতে, যেমনঃ একটি অ্যাপ্লায়েন্স, আমরা ধরে নিই যে এটির সুনির্দিষ্ট ফাংশনগুলির একটি সেট রয়েছে যা এটি সম্পাদন করতে পারে। উদাহরণস্বরূপ, একটি মাইক্রোওয়েভ ওভেনের আমাদের খাবার গরম ও রান্না করার কথা এবং এর বেশি কিছু নয়। আমরা আশা করি না যে একটি মাইক্রোওয়েভ ওভেন কখনও আমাদের জন্য জামাকাপড় ধুতে সক্ষম হবে। একটি কম্পিউটিং মেশিন (একটি কম্পিউটার) আলাদা। আমরা আশা করি যে কোনও প্রোগ্রাম এটি সম্পাদন করবে-একটি কম্পিউটারের কার্যকারিতা এক্সটেনসিবল। যদি আমরা একটি কম্পিউটারকে একটি গাড়ির সঙ্গে তুলনা করি, তাহলে প্রোগ্রামাররা এমন চালক যারা গাড়িকে বিভিন্ন কাজ করতে বাধ্য করতে পারে (একটি নির্দিষ্ট পরিমাণে) এবং ব্যবহারকারীরা এমন যাত্রীদের মতো যারা গাড়ি যা করতে পারে তার সদ্ব্যবহার করে। এটি আরেকটি কারণ যার জন্য প্রত্যেকের কম্পিউটার প্রোগ্রামিং শেখা প্রয়োজন কারণ এটি আপনাকে কম্পিউটারকে ভিন্ন কিছু করার স্বাধীনতা দেয়।
অ্যালগরিদমের শুদ্ধতা
সম্পাদনাঅ্যালগরিদমগুলি কার্যকর হওয়ার জন্য অবশ্যই সঠিক হতে হবে। আমাদের অ্যালগরিদমগুলি প্রোগ্রাম তৈরি করে ব্যবহার করার আগে ত্রুটিগুলি অপসারণের জন্য আমাদের অবশ্যই যত্ন সহকারে পরীক্ষা করতে হবে। যদি কোনও অ্যালগরিদমের ত্রুটি থাকে, তাহলে সঠিক প্রোগ্রাম তৈরি করা অসম্ভব। আমরা প্রায়শই শিক্ষার্থীদের মনে করিয়ে দিই যে যদি তাদের অ্যালগরিদম সঠিক না হয় তবে তা কম্পিউটারে কাজ করবে না। সুতরাং আমাদের অবশ্যই প্রথমে আমাদের অ্যালগরিদমগুলি সঠিকভাবে তৈরি করতে হবে।
এমনকি একটি অ্যালগরিদমের নকশা সঠিক হলেও আমরা প্রোগ্রামিং প্রক্রিয়া চলাকালীন ত্রুটিগুলি প্রবর্তন করতে পারি। যে কোনও প্রাকৃতিক ভাষার মতো একটি প্রোগ্রামিং ভাষার নিজস্ব বাক্য গঠন রয়েছে যা ভাষা ব্যবহারের জন্য ব্যাকরণগত নিয়ম নিয়ে গঠিত। আমরা যখন এই নিয়মগুলি লঙ্ঘন করি তখন আমরা আমাদের প্রোগ্রামে সিনট্যাক্স ত্রুটিগুলি প্রবর্তন করি। এই ধরনের ত্রুটিগুলি সহজেই সংশোধন করা যায়, প্রকৃতপক্ষে বেশিরভাগ আধুনিক প্রোগ্রাম সম্পাদকরা এই ধরনের ত্রুটিগুলি সম্পর্কে আমাদের সনাক্ত করতে এবং সতর্ক করতে পারেন। আরেক ধরনের ত্রুটি হল যুক্তিগত ত্রুটি, যা ভাষার অপব্যবহারের ফলে হয়। অন্য কথায়, আমাদের ব্যাকরণগতভাবে সঠিক প্রোগ্রামটি অর্থবোধ করে না বা কম্পিউটারে ভুল অর্থবোধ করে না। উদাহরণস্বরূপ, সমস্ত বাক্য ব্যাকরণগতভাবে সঠিক হলেও একটি ধারণা অস্পষ্ট বা বিভ্রান্তিকর হতে পারে। আপনি হয়তো ভাবতে পারেন যে, যৌক্তিকভাবে প্রোগ্রাম চালানোর সময় কম্পিউটারও ভুল করতে পারে। এটি সত্য তবে খুব কমই বিশেষত ত্রুটি সনাক্তকরণ পদ্ধতিতে সজ্জিত আধুনিক কম্পিউটারগুলির ক্ষেত্রে এটি ঘটে। আমরা সাধারণত ধরে নিই যে কম্পিউটার ভুল করে না। যদি প্রোগ্রামটি সঠিক উত্তর তৈরি না করে, তবে এটি মানুষের ত্রুটির ফল।
আমরা লজিক এররসকে সফ্টওয়্যার বাগও বলি। আসল "বাগ" আসলে একটি হার্ডওয়্যার ব্যর্থতা-একটি ইলেক্ট্রোমেকানিকাল কম্পিউটারে ধরা পড়া একটি মথ। এখন বাগগুলি সাধারণত হার্ডওয়্যার এবং সফ্টওয়্যার উভয় ক্ষেত্রেই কম্পিউটার সিস্টেমে যে কোনও ত্রুটি/ব্যর্থতা বোঝাতে ব্যবহৃত হয়। যখন একটি কম্পিউটার প্রোগ্রাম বাগ হয়, তখন এটি ভুল ফলাফল বা ক্র্যাশ তৈরি করবে কারণ কম্পিউটার হয়তো জানে না যে এর পরে কী করতে হবে। আরও একটি সূক্ষ্ম বাগগুলি কম্পিউটার প্রোগ্রামটিকে কখনও শেষ করতে দেয়না, যা ইনফাইনাইট লুপ নামে পরিচিত, যা স্পষ্টতই আমরাদের আশা অনুযায়ী নয়।
মানুষ ভুল করে বলে বাগ প্রায় অনিবার্য। তাহলে, আমাদের প্রোগ্রামগুলির শুদ্ধতা নিশ্চিত করার জন্য আমরা কীভাবে বাগগুলি ঠিক করব? আমাদের প্রোগ্রামগুলির সঠিকতা যাচাই করার জন্য আমাদের অবশ্যই পরীক্ষা করতে হবে। একটি পরীক্ষায় একটি প্রোগ্রামে নমুনা ইনপুট এবং প্রোগ্রাম থেকে পছন্দসই আউটপুট থাকে। আমরা নমুনা ইনপুটের জন্য প্রোগ্রামের সাপেক্ষে একটি পরীক্ষা চালাতে পারি এবং প্রকৃত আউটপুট সংগ্রহ করতে পারি। যদি প্রকৃত আউটপুট পছন্দসই আউটপুটের সাথে মেলে তবে প্রোগ্রামটি পরীক্ষায় উত্তীর্ণ হয়, অন্যথায় তাদের প্রোগ্রামে বা পরীক্ষায় একটি বাগ থাকে। আমরা সাধারণত অ্যালগরিদমের বিভিন্ন অংশ অনুশীলন করতে পরীক্ষার একটি সেট (একটি টেস্ট স্যুট) ব্যবহার করি। এই প্রক্রিয়াটিকে ডিবাগিং বলা হয় যা নিম্নলিখিত ছদ্ম কোডে প্রকাশ করা হয়েছেঃ
টেস্ট স্যুটের প্রতিটি পরীক্ষার জন্য
রান করুন এবং প্রকৃত আউটপুটটি পছন্দসই আউটপুটের সাথে তুলনা করুন
যদি তা মেলে তবে পরবর্তী পরীক্ষায় যান
অন্যথায় বাগটি ঠিক করুন এবং পুরো প্রক্রিয়াটি পুনরাবৃত্তি করুন
লক্ষ্য করুন যে খুব সহজ প্রোগ্রামগুলি ছাড়া আমাদের পরীক্ষাগুলি সম্পূর্ণ করা খুব কঠিন। যখন একটি প্রোগ্রাম বড় এবং আরও জটিল হয়ে ওঠে তখন সমস্ত সম্ভাব্য ক্ষেত্রে পরীক্ষার সংখ্যা খুব দ্রুত বৃদ্ধি পায়। ডিজকস্ট্রা যেমন বলেছিলেন, "প্রোগ্রাম টেস্টিং বাগের উপস্থিতি দেখানোর জন্য ব্যবহার করা যেতে পারে, কিন্তু কখনও তাদের অনুপস্থিতি দেখানোর জন্য নয়!" প্রোগ্রামগুলির শুদ্ধতা প্রমাণ করার জন্য কৌশল রয়েছে। উদাহরণস্বরূপ, কম্পিউটার প্রসেসরের জন্য মাইক্রোকোড প্রায়শই আনুষ্ঠানিক যাচাইয়ের মাধ্যমে সঠিক প্রমাণিত হয়।
অ্যালগরিদমের "ধর্ম"
সম্পাদনাসাধারণত একই সমস্যা সমাধানের জন্য সর্বদা একাধিক উপায় থাকে এবং তাই, কম্পিউটারকে আমাদের জন্য সমস্যা সমাধান করার জন্য একাধিক অ্যালগরিদম রয়েছে। সমস্যাটি সঠিকভাবে সমাধান করার পাশাপাশি আমরা একই সমস্যা সমাধানকারী অ্যালগরিদমগুলির তুলনা/মূল্যায়ন করতে সক্ষম হতে চাই। আমাদের অবশ্যই অ্যালগরিদম নকশায় "ধর্ম"-এর মানদণ্ড/পরিমাপ নির্ধারণ করতে হবে। এই ধরনের মানদণ্ড বা ব্যবস্থাগুলির মধ্যে সরলতা, বাস্তবায়নের সহজতা, বাস্তবায়নের গতি বা উত্তরগুলির যথার্থতা অন্তর্ভুক্ত থাকতে পারে। কম্পিউটিং-এ আমরা সমাধানের গতি সম্পর্কে সবচেয়ে বেশি যত্নশীল কারণ একটি দ্রুত অ্যালগরিদম একই সময়ের মধ্যে বৃহত্তর সমস্যা বা আরও বেশি সমস্যা সমাধান করতে পারে। এটি দক্ষতা নামেও পরিচিত-অনেক প্রক্রিয়ার একটি অর্থনৈতিক পরিমাপ। প্রায়শই অনেক প্রোগ্রামের উপযোগিতা ফলাফলের সময়োপযোগীতার উপর নির্ভর করে। উদাহরণস্বরূপ, একটি প্রোগ্রাম যা পরের দিনের আবহাওয়ার পূর্বাভাস দিতে ২৪ ঘন্টা সময় নেয় তা প্রায় অকেজো।
একটি অ্যালগরিদম দেওয়া হলে আমরা কীভাবে এর "গতি" পরিমাপ করব? একটি সম্ভাব্য পদ্ধতি হল অ্যালগরিদম বাস্তবায়ন করা, ফলাফলের জন্য প্রোগ্রাম চালানো এবং এর কার্যকরকরণের সময় পরিমাপ করা-যা একটি প্রোগ্রাম চালানোর শুরু এবং শেষের মধ্যে অতিবাহিত সময়। এই পদ্ধতিতে কিছু চ্যালেঞ্জ রয়েছে। প্রথমে অ্যালগরিদম প্রয়োগ করতে হবে, যা একটি গুরুতর প্রয়োগ হতে পারে। দ্বিতীয়ত, তাদের কার্যকর সময় তুলনা করার জন্য দুটি প্রোগ্রাম চালানোর জন্য আমাদের অবশ্যই তাদের একই ইনপুট (এ.কে.এ একটি ওয়ার্কলোড, যেমন: এক মিলিয়ন সংখ্যার তালিকা সর্টেড করতে হবে) এবং ইনপুটটির আকার কখনই আদর্শ নয়। তৃতীয়ত, একটি চলমান প্রোগ্রামের "গতি" কার্যকর পরিবেশ দ্বারা প্রভাবিত হয়, যেমন মেশিনের হার্ডওয়্যার কনফিগারেশন। উদাহরণস্বরূপ যেকোনো একটি প্দ্ধতি নিন। বিভিন্ন কর্তা অবশ্যই এটি অনুসরণ করে বিভিন্ন সময় ব্যয় করবে। প্রয়োজনীয় খাবারের পরিমাণ অবশ্যই পার্থক্যকে বাড়িয়ে তুলবে-আমরা উপাদানগুলির পরিমাণ বাড়ার সাথে সাথে দীর্ঘ রেসিপিগুলি অনুসরণ করতে আরও বেশি সময় লাগবে। তবে পদ্ধতিগুলি্র অন্তর্নিহিত বৈশিষ্ট্য রয়েছে যা প্রস্তুতির সময়কে প্রভাবিত করে। যদি কোনও রেসিপি ডিম ভাঙ্গা্র সাথে জড়িত থাকে তবে রাঁধুনিকে প্রতিটি ডিম ভেঙে আলাদাভাবে স্ক্র্যাম্বল করার নির্দেশ দিতে পারেন বা প্রথমে সমস্ত ডিম ভেঙে একসাথে স্ক্র্যাম্বল করতে পারেন। স্পষ্টতই প্রথম পদ্ধতিটি জড়িত অতিরিক্ত পদক্ষেপের কারণে ধীর। গণ্নায় এ অ্যালগরিদমগুলি অনুরূপ বৈশিষ্ট্য প্রদর্শন করে। মনে রাখবেন যে অ্যালগরিদমগুলি অবশ্যই কম্পিউটারগুলি সম্পাদন করতে পারে এমন কাজের ইউনিট (ধাপ) এর পরিপ্রেক্ষিতে সংজ্ঞায়িত করা উচিত যাতে এগুলি প্রোগ্রামিং ভাষায় প্রয়োগ করা সহজ হয়। অ্যালগরিদমগুলিতে যেভাবে ধাপগুলি সাজানো এবং সংগঠিত করা হয় তা অ্যালগরিদমগুলি বাস্তবায়িত প্রোগ্রামগুলির কার্যকর করার সময়কে উল্লেখযোগ্যভাবে প্রভাবিত করতে পারে।
যেহেতু একটি অ্যালগরিদম একটি সমস্যার ধারণাগত সমাধান, তাই আমরা তাদের "গতি" প্রকৃতপক্ষে প্রয়োগ না করে একটি বিমূর্ত অর্থে অধ্যয়ন করতে চাই। এটি কম্পিউটার বিজ্ঞানে অ্যালগরিদম বিশ্লেষণ নামে পরিচিত। এই পদ্ধতিতে আমরা সিউডো কোড বা ফ্লো চার্টে বর্ণিত একটি অ্যালগরিদম নিই, ধাপের সংখ্যা (কাজের একক) গণনা করি যা সর্বদা ইনপুট আকারের একটি ফাংশন। পূর্বোক্ত উদাহরণের পদ্ধটিতে প্রথম পদ্ধতিটি অনুসরণ করতে যে সময় লাগে (প্রতিটি ডিম ভেঙে আলাদাভাবে স্ক্র্যাম্বল করা হয়) তা সরাসরি ডিমের সংখ্যার সাথে আনুপাতিক। প্রকৃতপক্ষে যদি শুধুমাত্র একটি ডিমের প্রয়োজন হয়, তবে দুটি পদ্ধতির মধ্যে কোনও পার্থক্য নেই। একটি নির্দিষ্ট ইনপুট আকারের জন্য গৃহীত পদক্ষেপগুলি পরিমাপ করার পরিবর্তে, আমরা পদক্ষেপের সংখ্যা এবং ইনপুট আকারের মধ্যে সম্পর্ক ফাংশনের দিকে মনোনিবেশ করি, যা ইনপুট আকার বৃদ্ধির সাথে সাথে কাজের পরিমাণ (ব্যয়) বৃদ্ধির ধরণটি দেখায়। এই ধরনের ফাংশনগুলি বৃদ্ধি ফাংশন নামেও পরিচিত। তারপরে, আমরা অ্যাসিম্পটোটিক বিশ্লেষণ প্রয়োগ করি, যা ফাংশনগুলিকে সহজতর করার জন্য ইনপুটগুলি অসীমের দিকে এগিয়ে যাওয়ার সাথে সাথে ফাংশনগুলির তুলনা করে, কারণ ইনপুটের আকার অসীমের দিকে এগিয়ে যাওয়ার সাথে সাথে কাজের ইউনিটগুলির মধ্যে পার্থক্য অদৃশ্য হয়ে যায় (আমরা ধরে নিতে পারি যে একটি ডিম ভেঙে এবং স্ক্র্যাম্বলিং করতে একই পরিমাণ সময় লাগে) এবং কাজের বেশিরভাগ "জটিল" অংশের ব্যয় আধিপত্য বিস্তার করবে (যে অংশটি ধাপে ১০এর পুনরাবৃত্তি করে তা যে কোনও পদক্ষেপকে ছোট করবে যা কেবল একবার করা হয়। মোট ব্যয়ঃ উদাহরণস্বরূপ, একটি পদ্ধতি আমাদের একটি দ্রুত পদক্ষেপ (প্রতি পরিবেশনায় ০.০০০১ সেকেন্ড সময় নেয়) যা ১০ বার পুনরাবৃত্তি করে এবং একটি ধীর পদক্ষেপ (প্রতি পরিবেশনায় ১০ সেকেন্ড সময় নেয়) পুনরাবৃত্তি করে না, এন (ইনপুট আকার) পরিবেশন করার পরিমাণ ০.০০০১ ∗ ১০ ∗ N পুনরাবৃত্ত পদক্ষেপে মোট সেকেন্ড এবং সর্বদা ধীর পদক্ষেপে ১০সেকেন্ড ব্যয় হবে। যখন N ১০০০০ এর চেয়ে বড় হয়, তখন পুনরাবৃত্ত অংশটির মান ধীর অংশের চেয়ে বেশি হবে। অ্যাসিম্পটোটিক বিশ্লেষণে আমরা ধীর পদক্ষেপটিকে উপেক্ষা করতে পারি কারণ N যখন অনন্তের কাছে পৌঁছায় তখন মোট ব্যয়ে এর অবদান নগণ্য। বৃদ্ধির ক্রিয়াকলাপগুলি সহজ করার মাধ্যমে আমরা তাদের প্রতিটি বিভাগের অ্যালগরিদম বিবেচনা করে বিভাগগুলিতে রাখতে পারি যাতে একই কর্মক্ষমতা বৈশিষ্ট্য থাকে। এই ধরনের বিশ্লেষণ সম্পূর্ণরূপে সুনির্দিষ্ট নয় তবে এটি অ্যালগরিদমের প্রকৃতি অধ্যয়ন করতে এবং তাদের কর্মক্ষমতা পূর্বাভাস দিতে খুব কার্যকর হতে পারে। আমরা শিখি কিভাবে অ্যালগরিদমকে বিভিন্ন বিভাগে রাখা যায় এবং তাদের পারফরম্যান্সকে তাদের বিভাগ অনুযায়ী শ্রেণীবদ্ধ করা যায়। আমরা প্রতিটি বিভাগকে বড় হাতের O ব্যবহার করে চিহ্নিত করি।
সংক্ষেপে আমরা অ্যালগরিদম জটিলতা বিশ্লেষণ সম্পর্কিত নিম্নলিখিত কয়েকটি মূল ধারণা নিয়ে আলোচনা করেছিঃ
- অ্যালগরিদমগুলি হল সমস্যাগুলির ধারণাগত এবং বিমূর্ত সমাধান এবং প্রোগ্রামগুলি হল বিমূর্ত এক্সিকিউটেবল কোড যা কম্পিউটারগুলি চালাতে পারে। আমরা কম্পিউটারে অ্যালগরিদম চালাতে পারি না; আমরা কেবল প্রোগ্রাম চালাতে পারি যা অ্যালগরিদম প্রয়োগ করে। অতএব, একটি অ্যালগরিদমের কর্মক্ষমতা সংজ্ঞা দ্বারা বিমূর্ত।
- একটি অ্যালগরিদমের ধর্ম পরিমাপ অ্যালগরিদমের একটি অন্তর্নিহিত বৈশিষ্ট্য হতে হবে-এমন কিছু যা বাস্তবায়নের বিশদ বিবরণ এবং ভবিষ্যতের কার্যকর পরিবেশ নির্বিশেষে নকশার "কার্যকা্রিতা" প্রতিফলিত করে।
- অর্থনৈতিক দৃষ্টিকোণ থেকে আমরা সময় এবং স্থান উভয় ক্ষেত্রেই অ্যালগরিদমের ব্যয় নিয়ে চিন্তা করি। আমরা এই কোর্সে শুধুমাত্র সময় ব্যয়ের দিকে মনোনিবেশ করব। আমরা আসলে অ্যালগরিদমের সময় ব্যয় পরিমাপ করতে পারি না, তবে আমরা সময় ব্যয় এবং ইনপুট আকারের মধ্যে সম্পর্ক অধ্যয়ন করতে পারি, যা অ্যালগরিদমের অভ্যন্তরীণ জটিলতা (বা চতুরতা) প্রতিফলিত করে। আমরা পরিবর্তনশীল হিসাবে ইনপুট আকার এবং মূল্য হিসাবে মোট ব্যয়ের সাথে বৃদ্ধির ক্রিয়াকলাপের মতো সম্পর্কের প্রতিনিধিত্ব করি। বৃদ্ধির ক্রিয়াকলাপগুলি কেবলমাত্র প্রভাবশালী শব্দ (অ্যাসিম্পটোটিক বিশ্লেষণ) রেখে সরলীকৃত করা যেতে পারে কারণ ইনপুটটি যখন সত্যিই বড় হয়ে যায় তখন অন্যান্য পদগুলি কোন ব্যাপার না। সরলীকৃত বৃদ্ধি ফাংশনগুলি বিভাগগুলিতে রাখা হয় এবং অ্যালগরিদমগুলি তাদের অন্তর্গত বিভাগগুলির দ্বারা র্যাঙ্ক করা যেতে পারে।
- কম জটিলতা বিভাগের অ্যালগরিদমগুলি উচ্চতর জটিলতা বিভাগের অ্যালগরিদমগুলির চেয়ে ভাল পারফর্ম করবে যখন ইনপুটের আকার যথেষ্ট বড় হয়। আমরা বড় আকারের ইনপুট নিয়ে চিন্তা করি কারণ যে কোনও অ্যালগরিদম একটি ছোট সমস্যা দ্রুত সমাধান করতে পারে। এই অ্যালগরিদম বিশ্লেষণ কৌশলের সাহায্যে আমরা অ্যালগরিদমগুলির মূল্যায়ন এবং তুলনা করতে পারি যাতে এগুলির কোনওটি বাস্তবায়নের আগে এই জাতীয় অ্যালগরিদম প্রয়োগকারী প্রোগ্রামগুলির আপেক্ষিক কার্যকারিতা পূর্বাভাস দেওয়া যায়।
- দক্ষতা, একটি শব্দ হিসাবে প্রায়শই ব্যবহৃত হয়, যা জটিলতার বিপরীত আনুপাতিক। একটি আরও জটিল অ্যালগরিদম কম দক্ষ কারণ এটি আরও জটিল হয়ে গ্ণনা্র সংস্থানগুলির কম দক্ষভাবে ব্যবহার করে।
উদাহরণ
সম্পাদনা১ এবং N এর মধ্যে সমস্ত সংখ্যার যোগফল গণনা করার অন্তত দুটি উপায় রয়েছে। নীচে দুটি অ্যালগরিদম রয়েছেঃ
- অ্যালগরিদম ১: সমস্ত সংখ্যা ম্যানুয়ালি যোগ করুন, একের পর এক
- অ্যালগরিদম ২: এই সূত্র ((N + ১) ∗ ((N /২) ব্যবহার করে ফলাফল গণনা করুন
(N + ১) * (N/২) নিচের প্রশ্নটি বিবেচনা করুনঃ যদি আমরা ম্যানুয়ালি দুটি অ্যালগরিদম পরিচালনা করি, তবে কোনটি দ্রুত চলবে যদি
- N= ২?
- N = ১০০?
- N = ১,০০০,০০০?
আসুন দেখি কিভাবে একটি অ্যালগরিদম কম্পিউটারে (বাস্তবায়িত হওয়ার পরে) আচরণ করে। নিম্নলিখিত স্ক্রিপ্টটি একটি ব্লক ব্যবহার করে অ্যালগরিদম ১ প্রয়োগ করে যা পরিসীমার সমস্ত সংখ্যার মধ্য দিয়ে পুনরাবৃত্তি করে এবং একবারে যোগফলের সাথে যোগ করে।
অ্যালগরিদম ২ ব্যবহার করে একই সমস্যা সমাধান করা যেতে পারে, যা নিম্নলিখিত স্ক্রিপ্ট এবং রিপোর্ট ব্লকে দেখানো ফলাফল গণনা করতে একটি ফাংশন ব্যবহার করে।
উভয় স্ক্রিপ্ট (প্রোগ্রাম) একই ইনপুট নেয়-দুটি সংখ্যা যা একটি পরিসীমা নির্ধারণ করে। সীমার মধ্যে সংখ্যার সংখ্যা হল ইনপুট আকার বা আরও সঠিকভাবে সমস্যার আকার। আমরা ধরে নিই যে কাজের এককগুলি হল গাণিতিক অপারেশন + − ∗/, অ্যাসাইনমেন্ট অপারেশন এবং রিপোর্ট অপারেশন। এই ধরনের অনুমান যুক্তিসঙ্গত কারণ কাজে অপারেন্ড নির্বিশেষে সেই ক্রিয়াকলাপগুলি সম্পাদন করতে একই সময় নেয়। আপনি যদি প্রোগ্রামগুলি চালান এবং বিভিন্ন ইনপুট সাইজ চেষ্টা করেন তবে আপনি লক্ষ্য করবেন যে আপনি ইনপুট সাইজ বাড়ানোর সাথে সাথে প্রথম প্রোগ্রামের এক্সিকিউশন সময় অবিচ্ছিন্নভাবে বৃদ্ধি পায় যেখানে দ্বিতীয় প্রোগ্রামটি এক্সিকিউশন টাইমে কোনও পরিবর্তন দেখায় না। আমরা কি এই ধরনের আচরণের পূর্বাভাস দিতে পারি?
আসুন এই দুটি অ্যালগরিদমে অ্যালগরিদম বিশ্লেষণ প্রয়োগ করি। প্রথম অ্যালগরিদম যোগফল পেতে সংখ্যার মধ্য দিয়ে লুপ করে, তাই ব্যয় (ধাপের সংখ্যা-সংযোজন) এবং ইনপুট আকারের মধ্যে সম্পর্ক ফাংশন হল f = a + b ∗ N ধরে নেওয়া N ইনপুট আকার এবং a এবং b স্ক্রিপ্ট পরিবর্তনশীল এবং একটি সংযোজনের জন্য ব্যয় তৈরি করার খরচ। লক্ষ্য করুন যে a এবং b উভয়ই ধ্রুবক কারণ তারা একটি প্রদত্ত কম্পিউটারের জন্য পরিবর্তিত হয় না। আমরা কেবল f = N ফাংশনটি করতে পারি কারণ যখন N অসীমের কাছে পৌঁছায় তখন ধ্রুবকগুলি আর গুরুত্বপূর্ণ হয় না। আমরা O (N) দ্বারা চিহ্নিত। আরেকটি সমস্যা বিবেচনা করা যাকঃ একটি তালিকার সংখ্যা কি আলাদা? এখানে ফেক কোডে একটি সোজা অগ্রবর্তী অ্যালগরিদম রয়েছেঃ
- পদক্ষেপ ১: তালিকার অন্যান্য সমস্ত সংখ্যার সাথে প্রথম সংখ্যাটির তুলনা করুন। যদি, যে কোনও সময়ে, একই সংখ্যাটি দেখা যায়, তাহলে থামুন এবং 'না' উত্তর দিন।
- পদক্ষেপ ২: তালিকা থেকে পরবর্তী সংখ্যাটি নিয়ে এবং অন্যান্য সমস্ত সংখ্যার সাথে তুলনা করে পদক্ষেপ ১ পুনরাবৃত্তি করুন।
- পদক্ষেপ ৩: তালিকার সমস্ত সংখ্যা ব্যবহার করার পরে, থামুন এবং হ্যাঁ উত্তর দিন। লগরিদমের মধ্যে এই ধরনের বৃদ্ধি ফাংশন সহ অ্যালগরিদম বরাদ্দ করি। দ্বিতীয় অ্যালগরিদম সর্বদা একই পরিমাণ সময় নেয় কারণ এটি ইনপুট আকার নির্বিশেষে একই ক্রিয়াকলাপ সম্পাদন করে। এটি ০ (১) দ্বারা চিহ্নিত ধ্রুবক সময় বিভাগের অন্তর্গত।
ইনপুটের আকার হল তালিকার আকার। তালিকায় যত বেশি সংখ্যা থাকবে, প্রশ্নের উত্তর দিতে তত বেশি সময় লাগবে। অ্যালগরিদম অনুসারে এটি সম্ভব যে প্রথম তুলনা দুটি অভিন্ন সংখ্যা খুঁজে পায়, যা প্রশ্নের সঠিক উত্তর দেয়। এটি ভাল নকশা কারণ সেই সময়ে বাকি অ্যালগরিদমের চালিয়ে যাওয়া অপ্রয়োজনীয়। যখন আমরা অ্যালগরিদমগুলি বিশ্লেষণ করি তখন আমরা সবচেয়ে খারাপ ক্ষেত্রে মনোনিবেশ করি কারণ একটি অ্যালগরিদমের কর্মক্ষমতা প্রকৃত ইনপুট থেকে নির্ভরশীল এবং আমাদের ভাগ্যের উপর নির্ভর করা উচিত নয়! সুতরাং এই অ্যালগরিদমের জন্য ব্যয় এবং ইনপুট আকারের মধ্যে সম্পর্ক (বৃদ্ধি) ফাংশনটি হওয়া উচিত = f = N * (N-1) কারণ সবচেয়ে খারাপ ক্ষেত্রে (সমস্ত সংখ্যা অনন্য) অ্যালগরিদমকে প্রতিটি সংখ্যার সাথে তালিকার অন্যান্য সমস্ত সংখ্যার তুলনা করতে হবে। কেবলমাত্র সবচেয়ে বড় প্রভাবশালী পদটি রেখে আমরা ফাংশনটি পেতে পারি = যা অ্যালগরিদমটিকে চতুর্ভুজ বিভাগে রাখে = । আপনি যদি আগ্রহী হন তবে আপনি অ্যালগরিদমের পূর্বাভাস কর্মক্ষমতা বৈশিষ্ট্যগুলি যাচাই করতে নিম্নলিখিত স্ক্রিপ্টটি (অ্যালগরিদমের বাস্তবায়ন) পুনরুত্পাদন এবং চালাতে পারেন। আসুন অন্য বিভাগ থেকে একটি অ্যালগরিদম দেখিঃ সমস্ত এন-ডিজিট নম্বর প্রিন্ট করুন?
০, ১, ২, ৩,..., ৯-পর্যন্ত প্রতিটি সংখ্যার জন্য
প্রথম সংখ্যার জন্য সংখ্যাটি ব্যবহার করুন
সমস্ত এন-১ সংখ্যার সংখ্যা গণনা করুন
প্রতিটি এন-১ সংখ্যার সংখ্যাকে প্রথম সংখ্যার সাথে যুক্ত করে একটি এন সংখ্যা সংখ্যা তৈরি করুন।
এই উদাহরণটি কিছুটা কল্পিত তবে এটি একটি নতুন প্রক্রিয়া প্রদর্শন করে এবং যখন আমরা এনক্রিপশন কৌশলগুলি নিয়ে আলোচনা করি তখন এটি খুব কার্যকর। অ্যালগরিদমটি জটিল কারণ এটির আউটপুটের পরিমাণ (সমস্ত n-সংখ্যার সংখ্যা) উৎপন্ন করতে হয়। সুতরাং আউটপুট অংশের ব্যয় মোট ব্য্যকে প্রভাবিত করবে। সমস্ত n সংখ্যার সংখ্যা তৈরি করতে হলে আমাদের প্রথমে সমস্ত n-১ সংখ্যার সংখ্যা তৈরি করতে হবে। সমস্ত এন-১ সংখ্যার সংখ্যা তৈরি করতে আমাদের প্রথমে সমস্ত এন-২ সংখ্যার সংখ্যা তৈরি করতে হবে । পিছনের দিকে প্রক্রিয়াটি অধ্যয়ন করা সহজ। একটি সংখ্যা আউটপুট করা কাজের একক (এটি একটি সংখ্যা আউটপুট করতে একই সময় নেয়) ধরে নিলে সমস্ত একটি সংখ্যার সংখ্যা তৈরি করতে খরচ হয় ১০। সমস্ত দুটি সংখ্যার সংখ্যা তৈরি করতে আমাদের সংখ্যা আউটপুট করতে হবে। তিন অঙ্কের সংখ্যার জন্য খরচ । আপনি কি কোনও প্যাটার্ন দেখেছেন? সমস্ত n সংখ্যার সংখ্যা তৈরি করতে খরচ হয়। এই ধরনের অ্যালগরিদমগুলি চতুর্ভুজগুলির তুলনায় অনেক দ্রুত চলে কারণ ইনপুট আকারটি সূচকে থাকে। এগুলি হিসাবে চিহ্নিত এক্সপোনেনশিয়াল সময় বিভাগের অন্তর্গত। মূল (এই ক্ষেত্রে ২) কোন ব্যাপার না। কারণ সমস্ত এক্সপোনেনশিয়াল ফাংশন চতুর্ভুজ ফাংশন বা রৈখিক ফাংশন ছাড়া একে অপরের সাথে বেশি মিল।
এখানে একটি ইউটিউব ভিডিও রয়েছে যা বুদ্বুদ বাছাই অ্যালগরিদম এবং দ্রুত বাছাই অ্যালগরিদমের মধ্যে পারফরম্যান্সের পার্থক্য চিত্রিত করেঃ https://www.youtube.com/watch?v=aXXWXz5rF64