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

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

• জামাকাপড়
• পরিষ্কার
• ফেড

কোন অ্যালগরিদম আপনাকে এই ফলাফল অর্জন করতে দেয়?

1. একটি অ্যালার্ম ঘড়ি ব্যবহার করে জেগে উঠুন।
2. একটি স্নান নিন এবং নিজেকে ধুয়ে নিন।
3. সকালের নাস্তা এবং কিছু কফি বা চা তৈরি করুন।
4. খাওয়া.
5. আপনি যদি আগের সন্ধ্যায় আপনার জামাকাপড় ইস্ত্রি না করে থাকেন তবে সেগুলি ইস্ত্রি করুন।
6. পোশাক পরে নাও.
7. বাড়ি ছেড়ে চলে যান।

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

1. ওয়েবস্টারের তৃতীয় নতুন আন্তর্জাতিক অভিধানের 1961 সংস্করণটি কিনুন বা ডাউনলোড করুন।
2. এই অভিধানে আমাদের তালিকা থেকে প্রতিটি নাম খুঁজুন।
3. কাগজের টুকরোতে, অভিধানের পৃষ্ঠাটি লিখুন যেখানে নামটি অবস্থিত।
4. নামগুলি সাজানোর জন্য কাগজের টুকরা ব্যবহার করুন।

কর্মের এই ধরনের একটি ক্রম আমাদের টাস্ক সম্পন্ন হবে? হ্যাঁ, এটা অবশ্যই হবে। এই সমাধান কার্যকর ? কঠিনভাবে। এখানে আমরা অ্যালগরিদমের আরেকটি গুরুত্বপূর্ণ দিক নিয়ে আসি: তাদের কার্যকারিতা । এই কাজটি সম্পন্ন করার বিভিন্ন উপায় আছে। কিন্তু প্রোগ্রামিং এবং সাধারণ জীবনে উভয় ক্ষেত্রেই আমরা সবচেয়ে কার্যকর উপায় বেছে নিতে চাই। আপনার কাজ যদি টোস্টের একটি মাখনযুক্ত টুকরো তৈরি করা হয় তবে আপনি গম বপন এবং একটি গাভীকে দুধ দিয়ে শুরু করতে পারেন। কিন্তু যে একটি অদক্ষ হবেসমাধান — এতে অনেক সময় লাগবে এবং অনেক টাকা খরচ হবে। আপনি কেবল রুটি এবং মাখন কিনে আপনার সহজ কাজটি সম্পন্ন করতে পারেন। যদিও এটি আপনাকে সমস্যার সমাধান করতে দেয়, গম এবং একটি গরু জড়িত অ্যালগরিদম অনুশীলনে ব্যবহার করা খুব জটিল। প্রোগ্রামিং-এ, অ্যালগরিদমের জটিলতা মূল্যায়ন করার জন্য আমাদের কাছে বিগ ও নোটেশন নামে বিশেষ নোটেশন রয়েছে। বিগ ও একটি অ্যালগরিদমের কার্য সম্পাদনের সময় ইনপুট ডেটা আকারের উপর কতটা নির্ভর করে তা মূল্যায়ন করা সম্ভব করে । আসুন সহজ উদাহরণটি দেখি: ডেটা স্থানান্তর। কল্পনা করুন যে আপনাকে একটি ফাইল আকারে একটি দীর্ঘ দূরত্বে কিছু তথ্য পাঠাতে হবে (উদাহরণস্বরূপ, 5000 মাইল)। কি অ্যালগরিদম সবচেয়ে দক্ষ হবে? এটা নির্ভর করে আপনি যে ডেটা নিয়ে কাজ করছেন তার উপর। উদাহরণস্বরূপ, ধরুন আমাদের একটি অডিও ফাইল আছে যা 10 এমবি। এই ক্ষেত্রে, সবচেয়ে দক্ষ অ্যালগরিদম হল ইন্টারনেটের মাধ্যমে ফাইল পাঠানো। এটা কয়েক মিনিটের বেশি সময় নিতে পারে না! আসুন আমাদের অ্যালগরিদমটি পুনরুদ্ধার করি: "আপনি যদি 5000 মাইল দূরত্বে ফাইল আকারে তথ্য স্থানান্তর করতে চান তবে আপনাকে ইন্টারনেটের মাধ্যমে ডেটা পাঠাতে হবে"। চমৎকার। এখন এর বিশ্লেষণ করা যাক। এটা কি আমাদের টাস্ক সম্পন্ন?ওয়েল, হ্যাঁ, এটা করে. কিন্তু এর জটিলতা সম্পর্কে আমরা কী বলতে পারি? হুম, এখন জিনিসগুলি আরও আকর্ষণীয় হয়ে উঠছে। আসল বিষয়টি হল যে আমাদের অ্যালগরিদম ইনপুট ডেটার উপর খুব নির্ভরশীল, যথা, ফাইলের আকার। যদি আমাদের 10 মেগাবাইট থাকে, তাহলে সবকিছু ঠিক আছে। কিন্তু যদি আমাদের 500 মেগাবাইট পাঠাতে হয়? 20 গিগাবাইট? 500 টেরাবাইট? 30 পেটাবাইট? আমাদের অ্যালগরিদম কি কাজ করা বন্ধ করবে? না, এই সমস্ত পরিমাণ ডেটা সত্যিই স্থানান্তর করা যেতে পারে। এটা কি আর সময় লাগবে? হ্যা এটা হবে! এখন আমরা আমাদের অ্যালগরিদমের একটি গুরুত্বপূর্ণ বৈশিষ্ট্য জানি: পাঠাতে ডেটার পরিমাণ যত বেশি হবে, অ্যালগরিদম চালাতে তত বেশি সময় লাগবে. কিন্তু আমরা এই সম্পর্কের আরও সুনির্দিষ্ট ধারণা পেতে চাই (ইনপুট ডেটার আকার এবং এটি পাঠানোর জন্য প্রয়োজনীয় সময়ের মধ্যে)। আমাদের ক্ষেত্রে, অ্যালগরিদমিক জটিলতা রৈখিক । "লিনিয়ার" এর অর্থ হল ইনপুট ডেটার পরিমাণ যত বাড়বে, এটি পাঠাতে যে সময় লাগবে তা আনুপাতিকভাবে বৃদ্ধি পাবে। যদি ডেটার পরিমাণ দ্বিগুণ হয়, তবে এটি পাঠানোর জন্য প্রয়োজনীয় সময় দ্বিগুণ হবে। যদি ডেটা 10 গুণ বৃদ্ধি পায়, তবে সংক্রমণের সময় 10 গুণ বৃদ্ধি পাবে। বড় O স্বরলিপি ব্যবহার করে, আমাদের অ্যালগরিদমের জটিলতাকে O(n) হিসাবে প্রকাশ করা হয়. আপনার ভবিষ্যতের জন্য এই স্বরলিপিটি মনে রাখা উচিত — এটি সর্বদা রৈখিক জটিলতার সাথে অ্যালগরিদমের জন্য ব্যবহৃত হয়। মনে রাখবেন যে আমরা এখানে বিভিন্ন বিষয়ে কথা বলছি না: ইন্টারনেটের গতি, আমাদের কম্পিউটারের কম্পিউটেশনাল শক্তি এবং আরও অনেক কিছু। একটি অ্যালগরিদমের জটিলতা মূল্যায়ন করার সময়, এই কারণগুলি বিবেচনা করার অর্থ নেই - যে কোনও ক্ষেত্রে, এগুলি আমাদের নিয়ন্ত্রণের বাইরে। বিগ ও স্বরলিপি অ্যালগরিদমের জটিলতা প্রকাশ করে, এটি যে "পরিবেশ" এর মধ্যে চলে তা নয়। আসুন আমাদের উদাহরণ দিয়ে চালিয়ে যাই। ধরুন আমরা শেষ পর্যন্ত শিখেছি যে আমাদের মোট 800 টেরাবাইট ফাইল পাঠাতে হবে। আমরা, অবশ্যই, ইন্টারনেটের মাধ্যমে তাদের পাঠানোর মাধ্যমে আমাদের কাজটি সম্পন্ন করতে পারি। শুধু একটি সমস্যা আছে: স্ট্যান্ডার্ড পারিবারিক ডেটা ট্রান্সমিশন হারে (প্রতি সেকেন্ডে 100 মেগাবিট), এটি প্রায় 708 দিন সময় নেবে। প্রায় ২ বছর! :O আমাদের অ্যালগরিদম স্পষ্টতই এখানে উপযুক্ত নয়। আমাদের অন্য কোনো সমাধান দরকার! অপ্রত্যাশিতভাবে, আইটি জায়ান্ট অ্যামাজন আমাদের উদ্ধারে আসে! অ্যামাজনের স্নোমোবাইল পরিষেবা আমাদের মোবাইল স্টোরেজে প্রচুর পরিমাণে ডেটা আপলোড করতে দেয় এবং তারপরে ট্রাকে করে পছন্দসই ঠিকানায় পৌঁছে দিতে দেয়! সুতরাং, আমরা একটি নতুন অ্যালগরিদম আছে! "আপনি যদি 5000 মাইল দূরত্বে ফাইল আকারে তথ্য স্থানান্তর করতে চান এবং এটি করার জন্য ইন্টারনেটের মাধ্যমে পাঠাতে 14 দিনের বেশি সময় লাগবে, তাহলে আপনাকে একটি আমাজন ট্রাকে ডেটা পাঠাতে হবে।" আমরা এখানে নির্বিচারে 14 দিন বেছে নিয়েছি। ধরা যাক এটিই দীর্ঘতম সময় যা আমরা অপেক্ষা করতে পারি। আসুন আমাদের অ্যালগরিদম বিশ্লেষণ করি। তার গতি সম্পর্কে কি? এমনকি যদি ট্রাকটি মাত্র 50 মাইল বেগে ভ্রমণ করে তবে এটি মাত্র 100 ঘন্টায় 5000 মাইল অতিক্রম করবে। এই তো চারদিনের একটু বেশি! এটি ইন্টারনেটে ডেটা পাঠানোর বিকল্পের চেয়ে অনেক ভাল। এবং এই অ্যালগরিদম জটিলতা সম্পর্কে কি? এটা কি রৈখিক, অর্থাৎ O(n)? না এটা না. সর্বোপরি, ট্রাকটি আপনি এটিকে কতটা ভারীভাবে লোড করেন তা বিবেচনা করে না - এটি এখনও প্রায় একই গতিতে চালাবে এবং সময়মতো পৌঁছাবে। আমাদের 800 টেরাবাইট হোক বা তার 10 গুণ, ট্রাকটি এখনও 5 দিনের মধ্যে তার গন্তব্যে পৌঁছে যাবে। অন্য কথায়, ট্রাক-ভিত্তিক ডেটা ট্রান্সফার অ্যালগরিদমের ধ্রুবক জটিলতা রয়েছে. এখানে, "ধ্রুবক" মানে এটি ইনপুট ডেটা আকারের উপর নির্ভর করে না। ট্রাকে একটি 1GB ফ্ল্যাশ ড্রাইভ রাখুন, এটি 5 দিনের মধ্যে পৌঁছে যাবে। 800 টেরাবাইট ডেটা ধারণকারী ডিস্কে রাখুন, এটি 5 দিনের মধ্যে পৌঁছাবে। বড় O স্বরলিপি ব্যবহার করার সময়, ধ্রুবক জটিলতা O(1) দ্বারা চিহ্নিত করা হয় । আমরা O(n) এবং O(1) এর সাথে পরিচিত হয়েছি , তাই এখন প্রোগ্রামিংয়ের জগতে আরও উদাহরণ দেখি :) ধরুন আপনাকে 100টি সংখ্যার অ্যারে দেওয়া হয়েছে, এবং কাজটি হল তাদের প্রতিটিতে প্রদর্শন করা কনসোল আপনি একটি সাধারণ forলুপ লিখুন যা এই কাজটি সম্পাদন করে

int[] numbers = new int[100];
// ...fill the array with numbers

for (int i: numbers) {
   System.out.println(i);
}

এই অ্যালগরিদম জটিলতা কি? লিনিয়ার, অর্থাৎ O(n)। প্রোগ্রামটি অবশ্যই কতগুলি ক্রিয়াকলাপ সম্পাদন করবে তা নির্ভর করে এতে কতগুলি সংখ্যা পাস করা হয়েছে তার উপর। অ্যারেতে 100টি সংখ্যা থাকলে, 100টি অ্যাকশন থাকবে (স্ক্রীনে স্ট্রিংগুলি প্রদর্শনের জন্য বিবৃতি)। যদি অ্যারেতে 10,000টি সংখ্যা থাকে, তাহলে 10,000টি ক্রিয়া সম্পাদন করতে হবে। আমাদের অ্যালগরিদম কোন উপায়ে উন্নত করা যেতে পারে? না। যাই হোক না কেন, আমাদেরকে অ্যারের মধ্য দিয়ে N পাস করতে হবে এবং কনসোলে স্ট্রিং প্রদর্শন করতে N স্টেটমেন্ট চালাতে হবে। আরেকটি উদাহরণ বিবেচনা করুন।

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

আমাদের একটি খালি আছে LinkedListযার মধ্যে আমরা বেশ কয়েকটি সংখ্যা সন্নিবেশ করি। আমাদের উদাহরণে একটি একক সংখ্যা সন্নিবেশ করার অ্যালগরিদমিক জটিলতা LinkedListএবং কীভাবে এটি তালিকার উপাদানগুলির সংখ্যার উপর নির্ভর করে তা মূল্যায়ন করতে হবে। উত্তর হল O(1), অর্থাৎ ধ্রুবক জটিলতা । কেন? মনে রাখবেন যে আমরা তালিকার শুরুতে প্রতিটি সংখ্যা সন্নিবেশ করান। উপরন্তু, আপনি মনে রাখবেন যে আপনি যখন একটি সংখ্যা সন্নিবেশ করান LinkedList, উপাদানগুলি কোথাও সরে না। লিঙ্কগুলি (বা রেফারেন্স) আপডেট করা হয়েছে (যদি আপনি ভুলে যান যে লিঙ্কডলিস্ট কীভাবে কাজ করে, আমাদের পুরানো পাঠগুলির একটি দেখুন )। যদি আমাদের তালিকার প্রথম নম্বরটি হয় x, এবং আমরা তালিকার সামনে y নম্বরটি সন্নিবেশ করি, তাহলে আমাদের যা করতে হবে তা হল:

x.previous  = y;
y.previous = null;
y.next = x;

যখন আমরা লিঙ্কগুলি আপডেট করি, তখন আমরা চিন্তা করি না যে কতগুলি সংখ্যা ইতিমধ্যেই রয়েছেLinkedList , এক বা এক বিলিয়ন। অ্যালগরিদমের জটিলতা ধ্রুবক, অর্থাৎ O(1)।

লগারিদমিক জটিলতা

আতঙ্কিত হবেন না! :) যদি "লগারিদমিক" শব্দটি আপনাকে এই পাঠটি বন্ধ করতে এবং পড়া বন্ধ করতে চায়, তবে কয়েক মিনিট ধরে রাখুন। এখানে কোন পাগল গণিত হবে না (অন্য কোথাও এর মত প্রচুর ব্যাখ্যা আছে), এবং আমরা প্রতিটি উদাহরণ আলাদা করে নেব। কল্পনা করুন যে আপনার কাজ হল 100 সংখ্যার অ্যারেতে একটি নির্দিষ্ট সংখ্যা খুঁজে বের করা। আরো স্পষ্টভাবে, আপনি এটি আছে কি না তা পরীক্ষা করতে হবে। যত তাড়াতাড়ি প্রয়োজনীয় সংখ্যা পাওয়া যায়, অনুসন্ধান শেষ হয়, এবং আপনি কনসোলে নিম্নলিখিত প্রদর্শন করুন: "প্রয়োজনীয় সংখ্যা পাওয়া গেছে! অ্যারেতে এর সূচী = ...." আপনি কিভাবে এই কাজটি সম্পন্ন করবেন? এখানে সমাধানটি সুস্পষ্ট: আপনাকে প্রথম (বা শেষ থেকে) থেকে শুরু করে অ্যারের উপাদানগুলিকে একে একে পুনরাবৃত্তি করতে হবে এবং বর্তমান সংখ্যাটি আপনি যা খুঁজছেন তার সাথে মেলে কিনা তা পরীক্ষা করতে হবে। সেই অনুযায়ী, কর্মের সংখ্যা সরাসরি অ্যারের উপাদানের সংখ্যার উপর নির্ভর করে। আমাদের যদি 100টি সংখ্যা থাকে, তাহলে আমাদের সম্ভাব্যভাবে পরবর্তী উপাদানটিতে 100 বার যেতে হবে এবং 100টি তুলনা করতে হবে। যদি 1000টি সংখ্যা থাকে, তাহলে 1000টি তুলনা হতে পারে। এটি স্পষ্টতই রৈখিক জটিলতা, অর্থাৎO(n) । এবং এখন আমরা আমাদের উদাহরণে একটি পরিমার্জন যোগ করব: অ্যারে যেখানে আপনাকে সংখ্যাটি খুঁজে বের করতে হবে সেটি ঊর্ধ্বক্রম অনুসারে সাজানো হয়েছে । এটি কি আমাদের কাজের ক্ষেত্রে কিছু পরিবর্তন করে? আমরা এখনও পছন্দসই সংখ্যার জন্য একটি নৃশংস-শক্তি অনুসন্ধান সঞ্চালন করতে পারে. কিন্তু বিকল্পভাবে, আমরা সুপরিচিত বাইনারি অনুসন্ধান অ্যালগরিদম ব্যবহার করতে পারি । ছবির উপরের সারিতে, আমরা একটি সাজানো অ্যারে দেখতে পাচ্ছি। আমাদের এটিতে 23 নম্বরটি খুঁজে বের করতে হবে। সংখ্যার উপর পুনরাবৃত্তি করার পরিবর্তে, আমরা কেবল অ্যারেটিকে 2 ভাগে ভাগ করি এবং অ্যারের মধ্যের সংখ্যাটি পরীক্ষা করি। কক্ষ 4 এ অবস্থিত নম্বরটি খুঁজুন এবং এটি পরীক্ষা করুন (চিত্রের দ্বিতীয় সারি)। এই সংখ্যাটি 16, এবং আমরা 23 খুঁজছি। বর্তমান সংখ্যাটি আমরা যা খুঁজছি তার থেকে কম। ওটার মানে কি? এটা মানেসমস্ত পূর্ববর্তী সংখ্যাগুলি (যা 16 নম্বরের আগে অবস্থিত) চেক করার দরকার নেই : আমরা যেটি খুঁজছি তার থেকে সেগুলি কম হওয়ার নিশ্চয়তা, কারণ আমাদের অ্যারে সাজানো হয়েছে! আমরা বাকি 5টি উপাদানের মধ্যে অনুসন্ধান চালিয়ে যাচ্ছি। বিঃদ্রঃ:আমরা শুধুমাত্র একটি তুলনা করেছি, কিন্তু আমরা ইতিমধ্যে সম্ভাব্য বিকল্পগুলির অর্ধেক বাদ দিয়েছি। আমরা মাত্র 5 উপাদান বাকি আছে. আমরা আমাদের পূর্ববর্তী ধাপের পুনরাবৃত্তি করব বাকি সাব্যারেকে আবার অর্ধেক ভাগ করে আবার মাঝের উপাদান (চিত্রের ৩য় সারি) নিয়ে। সংখ্যাটি 56, এবং এটি আমরা যা খুঁজছি তার চেয়ে বড়। ওটার মানে কি? এর মানে হল যে আমরা আরও 3টি সম্ভাবনা বাদ দিয়েছি: 56 নম্বরটি নিজেই এবং এর পরে দুটি সংখ্যা (যেহেতু তারা 23-এর থেকে বেশি হওয়ার গ্যারান্টিযুক্ত, কারণ অ্যারেটি সাজানো হয়েছে)। আমাদের চেক করার জন্য মাত্র 2টি সংখ্যা বাকি আছে (চিত্রের শেষ সারি) — অ্যারে সূচক 5 এবং 6 সহ সংখ্যা। আমরা তাদের প্রথমটি পরীক্ষা করি এবং আমরা যা খুঁজছিলাম তা খুঁজে পাই — 23 নম্বর! এর সূচক ৫! আসুন আমাদের অ্যালগরিদমের ফলাফল দেখি, এবং তারপরে আমরা' এর জটিলতা বিশ্লেষণ করবে। যাইহোক, এখন আপনি বুঝতে পেরেছেন কেন এটিকে বাইনারি অনুসন্ধান বলা হয়: এটি বারবার ডেটাকে অর্ধেক ভাগ করার উপর নির্ভর করে। ফলাফল চিত্তাকর্ষক! যদি আমরা সংখ্যাটি খুঁজতে একটি রৈখিক অনুসন্ধান ব্যবহার করি, তাহলে আমাদের 10টি পর্যন্ত তুলনার প্রয়োজন হবে, কিন্তু একটি বাইনারি অনুসন্ধানের মাধ্যমে আমরা মাত্র 3টি দিয়ে কাজটি সম্পন্ন করেছি! সবচেয়ে খারাপ ক্ষেত্রে, 4টি তুলনা হবে (যদি শেষ ধাপে আমরা যে নম্বরটি চেয়েছিলাম তা প্রথমটির পরিবর্তে অবশিষ্ট সম্ভাবনার দ্বিতীয়টি ছিল। তাহলে এর জটিলতা সম্পর্কে কী হবে? এটি একটি খুব আকর্ষণীয় পয়েন্ট :) বাইনারি সার্চ অ্যালগরিদম লিনিয়ার সার্চ অ্যালগরিদম (অর্থাৎ সাধারণ পুনরাবৃত্তি) থেকে অ্যারের উপাদানের সংখ্যার উপর অনেক কম নির্ভরশীল। অ্যারেতে 10টি উপাদান সহ , একটি লিনিয়ার অনুসন্ধানের জন্য সর্বাধিক 10টি তুলনার প্রয়োজন হবে, তবে একটি বাইনারি অনুসন্ধানের জন্য সর্বাধিক 4টি তুলনার প্রয়োজন হবে৷ এটি 2.5 এর একটি ফ্যাক্টর দ্বারা একটি পার্থক্য। কিন্তু 1000টি উপাদানের একটি অ্যারের জন্য , একটি রৈখিক অনুসন্ধানের জন্য 1000টি পর্যন্ত তুলনার প্রয়োজন হবে, কিন্তু একটি বাইনারি অনুসন্ধানের জন্য প্রয়োজন হবে মাত্র 10টি ! পার্থক্য এখন 100 গুণ! বিঃদ্রঃ:অ্যারেতে উপাদানের সংখ্যা 100 গুণ বেড়েছে (10 থেকে 1000 পর্যন্ত), কিন্তু বাইনারি অনুসন্ধানের জন্য প্রয়োজনীয় তুলনার সংখ্যা মাত্র 2.5 (4 থেকে 10 পর্যন্ত) বৃদ্ধি পেয়েছে। যদি আমরা 10,000 উপাদানে পৌঁছাই , পার্থক্যটি আরও বেশি চিত্তাকর্ষক হবে: 10,000টি লিনিয়ার অনুসন্ধানের তুলনা এবং বাইনারি অনুসন্ধানের জন্য মোট 14টি তুলনা ৷ এবং আবার, যদি উপাদানের সংখ্যা 1000 গুণ বৃদ্ধি পায় (10 থেকে 10000 পর্যন্ত), তবে তুলনার সংখ্যা শুধুমাত্র 3.5 (4 থেকে 14 পর্যন্ত) একটি গুণক দ্বারা বৃদ্ধি পায়। বাইনারি সার্চ অ্যালগরিদমের জটিলতা হল লগারিদমিক , অথবা, যদি আমরা বড় O স্বরলিপি ব্যবহার করি, O(log n). এটা কেন বলা হয়? লগারিদম সূচকের বিপরীতের মত। বাইনারি লগারিদম হল এমন একটি শক্তি যার সাহায্যে একটি সংখ্যা পেতে হলে 2 নম্বর বাড়াতে হবে। উদাহরণস্বরূপ, আমাদের কাছে 10,000টি উপাদান রয়েছে যা আমাদের বাইনারি অনুসন্ধান অ্যালগরিদম ব্যবহার করে অনুসন্ধান করতে হবে। বর্তমানে, আপনি মান সারণী দেখতে পারেন যে এটি করার জন্য সর্বাধিক 14টি তুলনার প্রয়োজন হবে। কিন্তু যদি কেউ এই জাতীয় টেবিল সরবরাহ না করে এবং আপনাকে তুলনার সঠিক সর্বাধিক সংখ্যা গণনা করতে হবে? আপনাকে কেবল একটি সাধারণ প্রশ্নের উত্তর দিতে হবে: আপনার কোন শক্তিতে 2 নম্বর বাড়াতে হবে যাতে ফলাফলটি পরীক্ষা করা উপাদানগুলির সংখ্যার চেয়ে বেশি বা সমান হয়? 10,000 এর জন্য, এটি 14 তম শক্তি। 2 থেকে 13 তম ঘাত খুব ছোট (8192), কিন্তু 2 থেকে 14 তম শক্তি = 16384, এবং এই সংখ্যাটি আমাদের অবস্থাকে সন্তুষ্ট করে (এটি অ্যারের উপাদানগুলির সংখ্যার চেয়ে বড় বা সমান)। আমরা লগারিদম পেয়েছি: 14. আমাদের কতগুলি তুলনার প্রয়োজন হতে পারে! :) অ্যালগরিদম এবং অ্যালগরিদম জটিলতা খুব বিস্তৃত একটি বিষয় যা একটি পাঠের মধ্যে মাপসই করা যায় না৷ কিন্তু এটা জানা খুবই গুরুত্বপূর্ণ: অনেক চাকরির ইন্টারভিউতে অ্যালগরিদম যুক্ত প্রশ্ন থাকবে। তত্ত্বের জন্য, আমি আপনার জন্য কিছু বই সুপারিশ করতে পারি। আপনি " গ্রোকিং অ্যালগরিদম " দিয়ে শুরু করতে পারেন। এই বইয়ের উদাহরণগুলি পাইথনে লেখা, তবে বইটিতে খুব সহজ ভাষা এবং উদাহরণ ব্যবহার করা হয়েছে। এটি একজন শিক্ষানবিশের জন্য সেরা বিকল্প এবং আরও কী, এটি খুব বড় নয়। আরও গুরুতর পড়ার মধ্যে, আমাদের কাছে রবার্ট লাফোর এবং রবার্ট সেজউইকের বই রয়েছে. উভয়ই জাভাতে লেখা, যা আপনার জন্য শেখাকে একটু সহজ করে তুলবে। সর্বোপরি, আপনি এই ভাষার সাথে বেশ পরিচিত! :) ভাল গণিত দক্ষতার ছাত্রদের জন্য, সেরা বিকল্প হল টমাস কোরমেনের বই । কিন্তু একা তত্ত্ব আপনার পেট ভরবে না! জ্ঞান!= সক্ষমতা । আপনি HackerRank এবং LeetCode- এ অ্যালগরিদম জড়িত সমস্যা সমাধানের অনুশীলন করতে পারেন । এই ওয়েবসাইটগুলির কাজগুলি প্রায়ই Google এবং Facebook-এ সাক্ষাত্কারের সময়ও ব্যবহার করা হয়, তাই আপনি অবশ্যই বিরক্ত হবেন না :) এই পাঠের উপাদানটিকে আরও শক্তিশালী করার জন্য, আমি আপনাকে YouTube-এ বড় O স্বরলিপি সম্পর্কে এই দুর্দান্ত ভিডিওটি দেখার পরামর্শ দিচ্ছি৷ পরবর্তী পাঠে দেখা হবে! :)