অ্যালগরিদম এবং কীভাবে তাদের জটিলতা বিশ্লেষণ করবেন

অ্যালগরিদমগুলি আমরা প্রতিদিনের ভিত্তিতে প্রায় সমস্ত কার্যক্রমে জড়িত। তারা "কী" তারা কীভাবে ব্যবহার করছে বা "কীভাবে" আমরা সেগুলি ব্যবহার করি তা উপলব্ধি না করেই আমরা তাদের অনেকগুলি "স্বয়ংক্রিয়" উপর চালিত করি। সফ্টওয়্যার বিকাশে, এটি আলাদা নয়। তবে, যাইহোক আলগোরিদিমগুলি কী কী? এবং কেন তাদের জটিলতা বিশ্লেষণ করা গুরুত্বপূর্ণ?

খুঁজে বের কর! :)

অ্যালগরিদম কী?

কোনও কার্য সম্পাদনের জন্য প্রয়োজনীয় পদক্ষেপের একটি সেট।

কম্পিউটার প্রোগ্রামগুলি কেবলমাত্র অ্যালগরিদমগুলি চালিত করে না, সেগুলি আমাদের মানুষ দ্বারা কার্যকর ও কার্যকর করা হয়।

উদাহরণস্বরূপ, আপনি কি অ্যালগরিদমের কথা চিন্তা করেছেন যা নিম্নলিখিত কাজগুলি সম্পাদন করে?

  • দাঁত মাজো
  • গোসল কর
  • রাঁধুনি
  • বাড়ি থেকে কাজ চালান

আমাদের প্রতিদিনের দিনে, আমরা উপরে উল্লিখিত কমপক্ষে একটি কার্য সম্পাদন করার জন্য বিভিন্ন পদক্ষেপের ক্রিয়া সম্পাদন করি। আসুন উদাহরণস্বরূপ বাড়ি থেকে কাজ করার জন্য টাস্ক ড্রাইভিংটি ব্যবহার করুন। আমি যে পদক্ষেপগুলি নিই তা মূলত:

  1. আমার গাড়িতে উঠো
  2. তাদের যাত্রা শুরুর জন্য বন্ধুর বাড়িতে গাড়ি চালান
  3. আমি যেখানে অফিসে সেখানে গাড়ি চালাও
  4. আমার গাড়ি পার্কিং গ্যারেজে পার্ক করুন

এই কাজটি শেষ করার জন্য আমার প্রয়োজনীয় পদক্ষেপের (অ্যালগরিদম) সেট set

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

কম্পিউটার প্রোগ্রামগুলি খুব আলাদা নয়: বিভিন্ন ধরণের অ্যালগোরিদম রয়েছে যা বিভিন্ন কাজ সম্পাদন করতে ব্যবহার করা যেতে পারে। প্রায়শই, আমরা সেগুলি কী তা নিয়ে আমাদের নিজেদের উদ্বিগ্ন করি না, আমরা কেবল তাদের ব্যবহার করি (আমার অন্তর্ভুক্ত)।

উদাহরণস্বরূপ, ওয়াজে এবং গুগল ম্যাপস দ্বারা ব্যবহৃত অ্যালগরিদমটি কী এমন হওয়া উচিত যা দুটি অবস্থানের মধ্যে সেরা রুটটি গণনা করে? নেটফ্লিক্সের অ্যালগরিদম সম্পর্কে কী যা আপনি যা দেখেছেন তার উপর ভিত্তি করে সিনেমা এবং ধারাবাহিকের প্রস্তাব দেয়?

ব্যক্তিগতভাবে, আমি আপনাকে বলতে পারে না। তবে, আমি জানি যে তারা দক্ষ। দক্ষতা হ'ল একটি অ্যালগরিদমের জটিলতা বিশ্লেষণ করতে আমরা ব্যবহার করি।

অ্যালগরিদম জটিলতা কী?

কম্পিউটার বিজ্ঞানে, অ্যালগরিদম জটিলতা বলতে বোঝায় যে একটি কার্য সম্পাদন করতে একটি অ্যালগরিদম তার সময় এবং ইনপুটটির আকার অনুযায়ী কত সময় এবং স্থান ব্যয় করে।

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

সময়ের জটিলতার বিশ্লেষণ আমাদের নির্ধারণ করতে দেয় যে কোনও ইনপুট উপাদানগুলির বর্ধনের ফলে কোনও অ্যালগোরিদম কীভাবে আচরণ করবে। 10, 100 বা 1000 উপাদানগুলির প্রক্রিয়া করতে আমাদের যে সময় লাগে তা সম্পর্কে আমাদের ধারণা থাকতে পারে।

এবং কেন এই বিশ্লেষণ গুরুত্বপূর্ণ?

  • কোন অ্যালগরিদম সবচেয়ে দক্ষ তা নির্ধারণ করতে;
  • আরও দক্ষ অ্যালগরিদম বিকাশ করতে সক্ষম হতে;
  • একটি অ্যালগরিদমের গ্রন্থাগার, এমনকি এটি প্রকৃত ভাষাও দক্ষ কিনা তা বিশ্লেষণ করতে সক্ষম হতে।

সংক্ষেপে বলতে গেলে দক্ষতা বলতে পয়েন্ট!

সময় জটিলতা

একটি ক্রিয়াকলাপ শেষ হতে সময় লাগে।

আমরা ফ্রিকোয়েন্সি গণনা পদ্ধতি দিয়ে সময় বিশ্লেষণ শুরু করতে পারি, যা মেশিনের নির্দেশনাটি কার্যকরভাবে নির্ধারিত সময়ের সংখ্যা গণনা করে। প্রতিটি পদক্ষেপ (নির্দেশ) 1 দিয়ে শুরু করে একটি সময় ইউনিট বরাদ্দ করা হয়।

অ্যালগরিদম যে সময় গ্রহণ করে তা ফানসিওন ফ (এন) দ্বারা প্রকাশ করা হয়, যেখানে এন ডাটা আকারকে উপস্থাপন করে।

একটি বিশ্লেষণের ফলাফল নিম্নলিখিত হিসাবে প্রকাশ করা হয়:

([সময়টি প্রকাশ করে এমন ফাংশন]) = [সময়ের এককের যোগফল]

বাস্তবে এটি কীভাবে কাজ করে তা বুঝতে এখন কয়েকটি অ্যালগরিদম বিশ্লেষণ করা যাক।

প্রথম ফাংশন দুটি সম্পূর্ণ সংখ্যা যোগ করে:

আমরা দেখতে পাচ্ছি যে, কাজের জন্য, প্রয়োগকৃত অ্যালগরিদম শুধুমাত্র একটি পদক্ষেপ সম্পাদন করে: দুটি সংখ্যার যোগফল। যেহেতু আমরা প্রতিটি পদক্ষেপের জন্য একটি মানকে বিশিষ্ট করি, ফলাফলটি চ (এন) = 1।

আসুন পরবর্তী উদাহরণটি দেখুন, যা একটি অ্যালগরিদম যা অন্য পূর্ণসংখ্যার দ্বারা একটি পূর্ণসংখ্যা ভাগ করে দেয়:

সংখ্যার অনুরূপ গাণিতিক ক্রিয়াকলাপ হওয়া সত্ত্বেও, অ্যালগরিদমে আরও পদক্ষেপ রয়েছে কারণ এটি বিভাজক 0 কিনা তা পরীক্ষা করা দরকার; যদি এটি হয় তবে বিভাগটি উপলব্ধি করা হবে না। যেহেতু আমাদের মোট চারটি পদক্ষেপ রয়েছে এবং এর প্রত্যেকটির 1 টির জন্য মূল্য নির্ধারিত হয়েছে, ফলটি f (n) = 4।

পরবর্তী অ্যালগরিদম পূর্ণসংখ্যার তালিকার সমস্ত উপাদানকে যোগ করে দেয়:

এই অ্যালগরিদমে, একটি পদক্ষেপের অন্তর্ভুক্ত রয়েছে, পুনরাবৃত্তির জন্য একটি নির্দেশ; এর অর্থ হল এর জন্য কোডটি বেশ কয়েকবার কার্যকর করা হবে। যেহেতু মৃত্যুদন্ডের সংখ্যা ডেটা আকারের উপর নির্ভর করে, তাই আমরা n এর মানকে সময় ইউনিট হিসাবে চিহ্নিত করি। ফলাফল চ (এন) = 2 এন + 3।

পরবর্তী অ্যালগরিদম দ্বিতীয় তালিকার যোগের সাথে একটি তালিকার যোগ যোগ করে।

ফলস্বরূপ আমাদের কাছে f (n) = 2n² + 2n + 3 রয়েছে।

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

সাধারণত, যখন আমরা একটি অ্যালগরিদম বিশ্লেষণ করি তখন প্রক্রিয়া করার জন্য অনেক উপাদান থাকা অবস্থায় আমরা এর আচরণগুলি সন্ধান করার চেষ্টা করছি। এই পরিস্থিতিতে আমাদের সময় ইউনিটগুলির যোগফলের যোগসূত্রের প্রধান শব্দটি খুঁজে বের করতে হবে।

উদাহরণস্বরূপ, তৃতীয় অ্যালগরিদমের যোগফলের মূল শব্দটি কী?

f (n) = 2n + 3

এই ক্ষেত্রে, 2 * n এ প্রধান শব্দটি এবং আমি কেন তা ব্যাখ্যা করব!

N 1 (n> 1) এর চেয়ে বড় যে কোনও পরিস্থিতিতে, পণ্যটির (গুণনের ফল) ইতিমধ্যে যোগফলের দ্বিতীয় পদের চেয়ে বেশি মূল্যবান হবে।

কোনও কিছুর পরীক্ষা করুন: 1 এর চেয়ে বড় কোনও পূর্ণসংখ্যার সাথে বিকল্প এন করুন, এবং গুণন করুন।

শেষ অ্যালগরিদমের যোগফলের মূল শব্দটির কী হবে?

f (n) = 2n² + 2n + 3

এই ক্ষেত্রে, প্রধান শব্দটি 2 * n², কারণ যখন n> 1 হয়, পণ্যটি সর্বদা যোগফলের দ্বিতীয় এবং তৃতীয় শর্তের চেয়ে বেশি হয়। এগিয়ে যান, এটি পরীক্ষা!

তবে, অ্যালগরিদমের জটিলতা বিশ্লেষণ করার জন্য আরও সাধারণ উপায় রয়েছে, যেখানে ধ্রুবকগুলি এবং কম উল্লেখযোগ্য শর্তাদি উপেক্ষা করা হয়। এই পদ্ধতিকে অ্যাসিপটোটিক জটিলতা বলা হয় called

এখানেই জটিলতার অর্ডার প্লে হয়ে আসে, এটি নোটেশন-ও বা বিগ-ও নামেও পরিচিত।

বিগ-ও স্বরলিপি

প্রক্রিয়াজাত উপাদানগুলির সংখ্যা বাড়ার সাথে সাথে ক্রিয়াকলাপের বৃদ্ধির হার বিবেচনা করে একটি অ্যালগরিদম শ্রেণিবদ্ধ করতে ব্যবহৃত হয়।

বিগ-ও স্বরলিপিটি একটি ফাংশনও সংজ্ঞায়িত করে যা একটি অ্যালগরিদমের সময় জটিলতা প্রকাশ করে। এই প্রান্তে, এন অক্ষর ও এর একটি ফাংশন হিসাবে ব্যবহৃত হয়।

সর্বাধিক সাধারণ ক্লাসগুলি হ'ল:

  • ও (1) - নিয়মিত, উপাদানগুলির সংখ্যা বৃদ্ধির সাথে ক্রিয়াকলাপের সংখ্যা বৃদ্ধি পায় না
  • ও (লগ এন) - লোগারিদমিক, অপারেশনের সংখ্যা উপাদানগুলির সংখ্যার চেয়ে কম
  • ও (এন) - লিনিয়ার, উপাদানগুলির সংখ্যার সাথে আনুপাতিকভাবে অপারেশন সংখ্যা বৃদ্ধি পায়
  • ও (n²) চতুর্ভুজ, ক্রিয়াকলাপের সংখ্যা উপাদানগুলির সংখ্যার চেয়ে বেশি হবে
  • O (2 ^ n) - ক্ষতিকারক, উপাদানগুলির সংখ্যার তুলনায় ক্রিয়াকলাপের সংখ্যা দ্রুত বৃদ্ধি পায়
  • ও (এন!) - ফ্যাক্টরিয়াল, অপারেশনগুলির সংখ্যা খুব দ্রুত বৃদ্ধি পায়, এমনকি অল্প সংখ্যক উপাদানগুলির জন্য

নীচে, আমাদের কাছে একটি গ্রাফিক রয়েছে যা অপারেশনের বৃদ্ধির হারকে চিত্রের পরিমাণের পরিমাণের চিত্রিত করে:

গ্রাফিকটি নীচে শ্রেণিবদ্ধ করা হয়েছে:

  • রেড জোন ভয়ঙ্কর, এড়িয়ে চলুন!
  • কমলা জোন খারাপ, এড়ানোও!
  • হলুদ অঞ্চলটি ন্যায্য, যুক্তিসঙ্গত!
  • হালকা-সবুজ অঞ্চল ভাল, দুর্দান্ত!
  • গাark়-সবুজ অঞ্চল চমৎকার, সম্মিলন!

এখন, আমরা পূর্বে উল্লিখিত এলগোরিদিমগুলিকে শ্রেণিবদ্ধ করতে বিগ-ও স্বরলিপিটি ব্যবহার করতে যাচ্ছি, আমাদের গাইড হিসাবে সর্বদা তাদের প্রধান শব্দটি ব্যবহার করে।

প্রথম অ্যালগরিদমের ফলাফল চ (এন) = 1; এর অর্থ, উপাদানগুলির বৃদ্ধি ব্যতীত অ্যালগরিদম কেবল একটি অপারেশন চালায়। সুতরাং, আমরা কনস্ট্যান্ট - ও (1) হিসাবে অ্যালগরিদমকে শ্রেণিবদ্ধ করতে পারি।

দ্বিতীয় অ্যালগরিদমের ফলাফল এফ (এন) = 4; এর অর্থ, উপাদানগুলির বৃদ্ধি ব্যতীত অ্যালগরিদম চারটি ক্রিয়াকলাপ চালাবে। সুতরাং, আমরা এই অ্যালগরিদমকে কনস্ট্যান্ট - ও (1) হিসাবে শ্রেণিবদ্ধ করতে পারি।

তৃতীয় অ্যালগরিদমের ফলাফল ছিল চ (এন) = 2 এন + 3; এর অর্থ হল যে ক্রিয়াকলাপের সংখ্যা উপাদানগুলির সংখ্যার সাথে আনুপাতিকভাবে বৃদ্ধি পাবে, এন এই ফাংশনে কীভাবে ভেরিয়েবল হিসাবে কাজ করে তা দেখে। সুতরাং, আমরা এই অ্যালগরিদমকে লিনিয়ার - ও (এন) হিসাবে সংজ্ঞায়িত করতে পারি।

শেষ অ্যালগরিদমের ফলাফল এফ (এন) = 2 এন² + 2 এন + 3 এর ফলস্বরূপ, যার অর্থ ক্রিয়াকলাপের সংখ্যা উপাদানগুলির সংখ্যার চেয়ে বেশি বৃদ্ধি পাবে। এই ক্ষেত্রে, n একটি ভেরিয়েবল হিসাবেও কাজ করে তবে এটি দ্বিতীয় শক্তিতে (স্কোয়ার্ড) উত্থাপিত হয়। সুতরাং, আমরা এই অ্যালগরিদমকে চতুষ্কোণ - ও (n²) হিসাবে সংজ্ঞায়িত করতে পারি।

নীচের সারণীটি ক্রিয়াকলাপগুলির সংখ্যার বৃদ্ধি চিত্রিত করে কারণ এটি উপাদানগুলির সংখ্যার বৃদ্ধি সম্পর্কিত।

লক্ষ্য করুন যে একটি ক্ষতিকারক অ্যালগরিদমে, 16 টি উপাদানগুলির কমপক্ষে 65,5536 ক্রিয়াকলাপ হবে। বেশ বিরক্তিকর, তাই না?

সাধারণভাবে, বিশ্লেষণ প্রক্রিয়াটি আমরা যা করছিলাম ঠিক তেমনই: পদক্ষেপের সংখ্যা গণনা এবং প্রধান শব্দটি সনাক্তকরণ।

কিছু ট্রেন্ড আমরা পর্যবেক্ষণ করতে পারি:

  • পুনরাবৃত্তি লুপ নেই এমন অ্যালগরিদমগুলি ধ্রুবক হতে থাকে - হে (1)
  • অ্যালগরিদমগুলির পুনরাবৃত্তি লুপগুলি রয়েছে যতক্ষণ না তারা বাসা বেঁধে না থাকে ততক্ষণ লিনিয়ার হতে থাকে - ও (এন)
  • দুটি নেস্টেড পুনরাবৃত্তি লুপ রয়েছে এমন আলগোরিদিমগুলি চতুষ্কোণীয় হয় - O (n²)
  • একটি অ্যারের সূচীতে সরাসরি অ্যাক্সেস সাধারণত ও (1) (ধ্রুবক) হয়
  • তালিকা এক্সটেনশন পদ্ধতিগুলি গড়ে ও ও (এন) হয়। উদাহরণস্বরূপ: যেকোন, যোগফল এবং ফিল্টার।
  • বাবল সাজান, সন্নিবেশ সাজান এবং সিলেক্ট বাছাইয়ের মতো বাছাই করা অ্যালগরিদমগুলি সাধারণত ও (N O) হয়।

কীভাবে অ্যালগরিদমগুলিকে শ্রেণিবদ্ধ করা যায় তা জেনে আমাদের অ্যালগরিদমের দক্ষতা বা অদক্ষতা বিচার করার ক্ষমতা দেয়। অবশ্যই, আমরা এর সঠিক চলমান সময়টি সেকেন্ড, মিনিট বা ঘন্টার মধ্যে পরিমাপ করতে পারি না। এটি করার জন্য এটি কার্যকর করা, পরিমাপ করা এবং সেই অনুযায়ী পরিবর্তন করা দরকার needs অ্যালগরিদমগুলির জন্য এটি চালানোর জন্য ঘন্টা, বা এমনকি কয়েক দিন সময় লাগে কিনা তা কল্পনা করুন? কোন সুযোগ নেই!

আমি আশা করি যে আমি এই পোস্টের লক্ষ্যটি পূরণ করেছি, যা ফ্রিকোয়েন্সি গণনা এবং বিগ-ও পদ্ধতি ব্যবহার করে অ্যালগরিদম এবং তাদের বিশ্লেষণের একটি ওভারভিউ দেওয়া হয়েছিল।

অতিরিক্ত পড়ার উপাদান হিসাবে আমি নীচে কিছু রেফারেন্স রেখেছি!

তথ্যসূত্র:

ভিডিয়োস 1 থেকে 1.7

প্রযুক্তির মাধ্যমে marketণের বাজারে নতুনত্ব আনতে চান? আমরা আমাদের ক্রুতে যোগ দিতে সর্বদা নতুন লোকের সন্ধান করছি!

আমাদের প্রারম্ভিকাগুলি এখানে দেখুন।