রৈখিক অনুসন্ধান

কম্পিউটার বিজ্ঞানে রৈখিক অনুসন্ধান বা ক্রমিক অনুসন্ধান হল একটি তালিকার (array) উপাদানগুলো থেকে কোন একটি নির্দিষ্ট উপাদান খুঁজে বের করার পদ্ধতি। এই নির্দিষ্ট উপাদান খোঁজার জন্য ক্রমান্বয়ে তালিকার প্রতিটি উপাদান মিলিয়ে দেখতে হয় যতক্ষণ না ওই উপাদানটি খুঁজে পাওয়া যায় ততক্ষণ পর্যন্ত অথবা তালিকার শেষ উপাদান পর্যন্ত।

রৈখিক অনুসন্ধানের প্রবাহের চার্ট

খুব বেশি খারাপ হলে রৈখিক অনুসন্ধান রৈখিক সময়ে সম্পন্ন হয় এবং বড়জোর n সংখ্যক তুলনা সম্পন্ন করে, যেখানে n হলো তালিকাটিতে উপাদানের সংখ্যা (বা দৈর্ঘ্য)। যদি প্রতিটি উপাদান অনুসন্ধান করা সমসম্ভাব্য হয়, তাহলে রৈখিক অনুসন্ধানটির জন্য গড় তুলনাসংখ্যা হবে ${\displaystyle {\frac {n}{2}}}$।^[১] তবে প্রতিটি উপাদানের অনুসন্ধান সম্ভাব্যতা ভিন্ন ভিন্ন হলে গড় তুলনাসংখ্যায় তা প্রভাব ফেলতে পারে। রৈখিক অনুসন্ধানের ব্যবহারিক প্রয়োগ খুবই কম, কারণ অন্যান্য অনুসন্ধান অ্যালগরিদম ও পদ্ধতি (যেমন, বাইনারি অনুসন্ধান বা হ্যাশ টেবিল) সব ধরনের তালিকার জন্য তুলনামূলক দ্রুত অনুসন্ধান ফলাফল প্রদান করে (সংক্ষিপ্ত তালিকা ব্যতীত)।

অ্যালগরিদম

মূল অ্যালগরিদম

L₀, L₁ .....L_n-1 মানগুলোর একটি তালিকা L এবং অভীষ্ট মান T দেওয়া থাকলে, নিম্নলিখিত সাবরুটিনটি রৈখিক অনুসন্ধান ব্যবহার করে L তালিকাটিতে অভীষ্ট মান T -এর সূচক (তথা অবস্থান) খুঁজে বের করে।^[২]

1. i -এর মান ০ (শূন্য) -তে নির্ধারণ করুন।
2. যদি L_i = T হয় তবে অনুসন্ধান সফলভাবে সমাপ্ত হয়েছে; i -এর মান ফেরত দিন।
3. i -এর মান ১ (এক) বৃদ্ধি করুন।
4. যদি i < n হয় তবে ২য় ধাপে ফেরত যান। অন্যথায় অনুসন্ধানটি ব্যর্থ হয়েছে।

প্রান্তিক মানের (sentinel) মাধ্যমে

উপরের মূল আলগরিদমটি প্রতি পুনরাবৃত্তির (iteration) জন্য দুবার করে তুলনা সম্পন্ন করে: একটি L_i = T কিনা তা পরীক্ষা করে এবং অন্যটি i তালিকাটির কোন বৈধ সূচককে নির্দেশ করে কিনা তা পরীক্ষা করে। তালিকার শেষে T -এর সমান একটি অতিরিক্ত উপাদান L_n যোগ করে (যাকে প্রান্তিক মান বলা হয়) দ্বিতীয়বারের তুলনাটি বাদ দেওয়া যায়; ফলে অ্যালগরিদমটি দ্রুততর হয়। যদি তালিকার মধ্যে অভীষ্ট মানটি না থাকে তবে অনুসন্ধানটি প্রান্তিক মানে না পৌঁছানো পর্যন্ত চালু থাকবে।^[২]

1. i -এর মান ০ (শূন্য) -তে নির্ধারণ করুন।
2. যদি L_i = T হয় তবে ৪র্থ ধাপে যান।
3. i -এর মান ১ (এক) বৃদ্ধি করুন এবং ২য় ধাপে ফেরত যান।
4. যদি i < n হয় তবে অনুসন্ধান সফলভাবে সমাপ্ত হয়েছে; i -এর মান ফেরত দিন। নাহলে অনুসন্ধানটি ব্যর্থ হয়েছে।

ক্রমিক তালিকায়

এক্ষেত্রে তালিকাটিতে উপাদানসমূহ ক্রমানুসারে সাজানো থাকে, অর্থাৎ L₀ ≤ L₁ ... ≤ L_n-1। অনুসন্ধানের যে মুহূর্তে L_i -এর মান অভীষ্ট মানের তুলনায় বড় হয় তখনই তা সমাপ্তকরত তালিকাটিতে অভীষ্ট মানটির অনুপস্থিতির বিষয়টি আরও দ্রুতগতিতে নির্ণয় করা যায়। তবে এর জন্য অভীষ্ট মানের চেয়ে প্রান্তিকের মান বেশি হওয়া প্রয়োজন।^[২]

1. i -এর মান ০ (শূন্য) -তে নির্ধারণ করুন।
2. যদি L_i ≥ T হয় তবে ৪র্থ ধাপে যান।
3. i -এর মান ১ (এক) বৃদ্ধি করুন এবং ২য় ধাপে ফেরত যান।
4. যদি L_i = T হয় তবে অনুসন্ধান সফলভাবে সমাপ্ত হয়েছে; i -এর মান ফেরত দিন। নাহলে অনুসন্ধানটি ব্যর্থ হয়েছে।

সি কোড

  int i=0;
  for(i=0;i<n;i++)
  {
     if(a[i] == item)
     {
        printf("Found!");
        return 1;
     }
     else if(a[i]!= item)
         contiue;
  }
  printf("Not Found!");
  return 0;

বিশ্লেষণ

n সংখ্যক উপাদানের একটি তালিকার ক্ষেত্রে সর্বোত্তম পরিস্থিতি হল যখন অভীষ্ট মানটি তালিকার প্রথম উপাদানের সমান হয়, তখন কেবলমাত্র একটিমাত্র তুলনার প্রয়োজন হয়। সবচেয়ে খারাপ পরিস্থিতি হল যখন মানটি তালিকায় না থাকে বা তালিকার একেবারে শেষে থাকে, সেক্ষেত্রে n সংখ্যক তুলনার প্রয়োজন হয়।^[১]

যদি অভীষ্ট মানটি তালিকায় k সংখ্যক বার উপস্থিত থাকে এবং তালিকার সমস্ত বিন্যাসই সমসম্ভাব্য হয়, তাহলে প্রত্যাশিত তুলনাসংখ্যা হল:

${\displaystyle {\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}}$

উদাহরণস্বরূপ, k = 1 হলে এই মান হবে ${\displaystyle {\frac {n+1}{2}}}$। যাইহোক, যদি এটি আগে থেকেই জানা যায় যে অভীষ্ট মানটি তালিকায় অন্তত একবার উপস্থিত আছে, তবে সর্বোচ্চ n-1 সংখ্যক তুলনার প্রয়োজন হবে; সেক্ষেত্রে প্রত্যাশিত তুলনাসংখ্যা হল:

${\displaystyle \displaystyle {\frac {(n+2)(n-1)}{2n}}}$

(যেমন, n = 2 এর জন্য এই মান হল 1; যা 'একটি না হলে আরেকটি' এই অবস্থার নির্দেশ করে)।

উভয়ক্ষেত্রে, রৈখিক অনুসন্ধানের অসীমতটীয়ভাবে (asymptotically) সবচেয়ে খারাপ পরিস্থিতির পরিব্যয় (cost) এবং প্রত্যাশিত পরিব্যয় উভয়ই O(n) [বড় O লিখনপদ্ধতি নিবন্ধটি দেখুন]।

অসম সম্ভাব্যতা

অভীষ্ট মানটির তালিকার প্রথমদিকে থাকার সম্ভাবনা বেশি থাকলে রৈখিক অনুসন্ধানের কার্যকারিতা বৃদ্ধি পায়। সুতরাং, যদি কিছু মান অনুসন্ধান করার সম্ভাবনা অন্যদের তুলনায় বেশি হয় তবে তাদেরকে তালিকার প্রারম্ভে স্থানান্তর করলে তা অধিকতর ফলপ্রসূ হতে পারে।

বিশেষত, যখন তালিকার উপাদানগুলো ক্রমহ্রাসমান সম্ভাব্যতা অনুসারে সাজানো থাকে এবং এই সম্ভাব্যতাগুলো জ্যামিতিকভাবে বণ্টিত থাকে, তখন রৈখিক অনুসন্ধানের পরিব্যয় মাত্র O(1)। যদি তালিকার আকার n যথেষ্ট বড় হয়, তাহলে রৈখিক অনুসন্ধান দ্বিমিক বা বাইনারি অনুসন্ধানের চেয়ে দ্রুততর হবে, যার পরিব্যয় O(log n)।^[২]

প্রয়োগ

রৈখিক অনুসন্ধান সাধারণত বাস্তবায়ন করা খুব সহজ, এবং তখনই কার্যকরী হয় যখন তালিকাটিতে মাত্র কয়েকটি উপাদান থাকে বা একটি অসজ্জিত তালিকায় অনুসন্ধানটি করা হয়।^[১]

যখন একই তালিকাতে অনেকগুলি মান অনুসন্ধান করতে হয় তখন দ্রুততর পদ্ধতি ব্যবহার করার লক্ষ্যে প্রায়ই তালিকাটির প্রাক-প্রক্রিয়াজাতকরণের প্রয়োজন হয় এবং সেক্ষেত্রে রৈখিক অনুসন্ধান বেশ কাজে দেয়। উদাহরণস্বরূপ, কেউ তালিকাটিকে বিন্যস্ত করতে পারে ও বাইনারি অনুসন্ধান ব্যবহার করতে পারে, অথবা এটি থেকে একটি কার্যকর অনুসন্ধান উপাত্ত কাঠামো (search data structure) তৈরি করতে পারে। তালিকার উপাদান ঘন ঘন পরিবর্তিত হলে, পুনঃ পুনঃ বিন্যাসের কারণে লাভের চেয়ে সমস্যাই বেশি হতে পারে।

ফলস্বরূপ, যদিও তাত্ত্বিকভাবে অন্যান্য অনুসন্ধান অ্যালগরিদম (যেমন, বাইনারি অনুসন্ধান) রৈখিক অনুসন্ধানের চেয়ে দ্রুততর বাস্তবে অন্য কোন পদ্ধতির ব্যবহার মোটামুটি অসম্ভব হতে পারে, এমনকি মধ্য-আকারের তালিকার ক্ষেত্রেও (প্রায় ১০০টি উপাদান বা তার কম)। আরও বড় তালিকার ক্ষেত্রে কেবলমাত্র অন্যান্য দ্রুততর অনুসন্ধান পদ্ধতির ব্যবহারই যুক্তিযুক্ত, কারণ তালিকাটি যদি যথেষ্ট বড় হয় তবে প্রারম্ভিক প্রস্তুতির (বিন্যস্তকরণ) জন্য প্রয়োজনীয় সময় অনেকগুলো রৈখিক অনুসন্ধানের মোট সময়ের সাথে তুলনীয়।^[১][৩]