البحث الخطي

الموسوعة الحرة

في علم الحاسوب ، يُعد البحث الخطي أو البحث التسلسلي طريقةً للعثور على عنصر داخل قائمة . فهو يتحقق بشكل تسلسلي من كل عنصر من عناصر القائمة حتى يتم العثور على تطابق أو يتم البحث في القائمة بأكملها. [ 1 ]

يعمل البحث الخطي في زمن خطي في أسوأ الحالات ، ويُجري على الأكثر n مقارنة، حيث n هو طول القائمة. إذا كان احتمال البحث عن كل عنصر متساوياً، فإن البحث الخطي يُجري في المتوسط ​​n +1 / 2 مقارنة ، ولكن قد يتأثر هذا المتوسط ​​إذا اختلفت احتمالات البحث لكل عنصر. نادراً ما يكون البحث الخطي عملياً لأن خوارزميات ومخططات بحث أخرى ، مثل خوارزمية البحث الثنائي وجداول التجزئة ، تُتيح بحثاً أسرع بكثير لجميع القوائم باستثناء القوائم القصيرة. [ 2 ]

الخوارزمية

تتحقق خوارزمية البحث الخطي بالتسلسل من كل عنصر في القائمة حتى تجد عنصرًا يطابق القيمة المستهدفة. إذا وصلت الخوارزمية إلى نهاية القائمة، ينتهي البحث دون جدوى. [ 1 ]

الخوارزمية الأساسية

بالنظر إلى قائمة L من n عنصرًا بقيم أو سجلات L 0 .... L n −1 ، وقيمة الهدف T ، فإن الروتين الفرعي التالي يستخدم البحث الخطي للعثور على فهرس الهدف T في L. [ 3 ]

  1. اجعل قيمة i تساوي 0.
  2. إذا كانت قيمة Li تساوي T ، فإن البحث ينتهي بنجاح؛ ويتم إرجاع i .
  3. قم بزيادة قيمة i بمقدار 1.
  4. إذا كانت قيمة i أقل من n ، فانتقل إلى الخطوة 2. وإلا، فإن البحث ينتهي دون جدوى.

يمكننا تعريف ذلك في الشفرة الزائفة كما هو موضح أدناه، باستخدام إما نهج تكراري أو نهج تكراري. 

الدالة iterativeLinearSearch( list L, T) تقوم بما يلي: for i = 0 to length(L) do if L[i] == T then return i // إرجاع قيمة غير ناجحة (في هذه الحالة -1). إرجاع -1 الدالة recursiveLinearSearch( list L, T, i = 0) هي: إذا كان L[i] == [T] ، فأرجع i . إذا كان i > length(L) ، فأرجع إرجاع -1 // قيمة غير ناجحة. أعد البحث الخطي المتكرر (L، T، i = i + 1)

مع حارس

تُجري الخوارزمية الأساسية المذكورة أعلاه مقارنتين في كل تكرار: الأولى للتحقق مما إذا كان Li يساوي T ، والثانية للتحقق مما إذا كان i لا يزال يشير إلى فهرس صالح في القائمة. بإضافة سجل إضافي Ln إلى القائمة ( قيمة حارس ) يساوي الهدف، يمكن حذف المقارنة الثانية حتى نهاية البحث، مما يُسرّع الخوارزمية . سيصل البحث إلى قيمة الحارس إذا لم يكن الهدف موجودًا في القائمة. [ 4 ]

  1. اجعل قيمة i تساوي 0.
  2. إذا كانت قيمة Li = T ، فانتقل إلى الخطوة 4.
  3. قم بزيادة قيمة i بمقدار 1 وانتقل إلى الخطوة 2.
  4. إذا كانت قيمة i أقل من n ، فإن البحث ينتهي بنجاح؛ ويتم إرجاع i . وإلا، فإن البحث ينتهي بشكل غير ناجح.

يمكننا تعريف ذلك في الشفرة الزائفة كما هو موضح أدناه، باستخدام إما نهج تكراري أو نهج تكراري.

الدالة iterativeSentinelSearch( list L, T) تقوم بما يلي: for i = 0 to length(L) do if L[i] == T then if i < length(L) then return i else return -1 return -1 دالة البحث التكراري عن الحارس ( القائمة L، T، i = 0) هي: إذا كان i >= طول (L) فأرجع -1، وإذا كان L[i] == T فأرجع i، ثم أعد الدالة recursiveSentinelSearch(L، T، i = i + 1).

في جدول مرتب

إذا رُتِّبت القائمة بحيث يكون L₀ ≤ L₁ ... ≤ Lₙ₋₁ ، يُمكن للبحث أن يُثبت عدم وجود الهدف بسرعة أكبر من خلال إنهاء البحث بمجرد أن يتجاوز Lᵢ الهدف . يتطلب هذا التغيير وجود عنصر مراقبة أكبر من الهدف . [ 5 ]

  1. اجعل قيمة i تساوي 0.
  2. إذا كانت قيمة Li ≥ T ، فانتقل إلى الخطوة 4.
  3. قم بزيادة قيمة i بمقدار 1 وانتقل إلى الخطوة 2.
  4. إذا كانت قيمة Li تساوي T ، فإن البحث ينتهي بنجاح؛ ويتم إرجاع i . وإلا، فإن البحث ينتهي بشكل غير ناجح.

يمكننا تعريف ذلك في الشفرة الزائفة كما هو موضح أدناه، باستخدام إما نهج تكراري أو نهج تكراري.

دالة iterativeTableSearch( list L, T) تقوم بما يلي : لكل i من 0 إلى طول(L)، إذا كان L[i] >= T، إذا كان L[i] == T ، فأرجع i، وإلا فأرجع -1 .دالة البحث التكراري في الجدول ( قائمة L، T، i = 0) هي: إذا كان i >= طول (L) ، فأرجع -1 . إذا كان L[i] >= T، فأرجع i. إذا كان L[i] == T، فأرجع i. وإلا فأرجع -1. ثم أعد الدالة: recursiveTableSearch(L, T, i = i + 1).

تحليل

بالنسبة لقائمة تحتوي على n عنصرًا، تكون الحالة المثلى عندما تكون القيمة مساوية للعنصر الأول في القائمة، وفي هذه الحالة لا يلزم سوى مقارنة واحدة. أما الحالة الأسوأ فتكون عندما لا تكون القيمة موجودة في القائمة (أو تظهر مرة واحدة فقط في نهاية القائمة)، وفي هذه الحالة يلزم إجراء n مقارنة.

إذا تكررت القيمة المطلوبة k مرة في القائمة، وكانت جميع ترتيبات القائمة متساوية الاحتمال، فإن العدد المتوقع للمقارنات هو

{نلو ك=0ن+1ك+1لو 1≤ك≤ن.{\displaystyle {\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}}

على سبيل المثال، إذا ظهرت القيمة المطلوبة مرة واحدة في القائمة، وكانت جميع ترتيبات القائمة متساوية الاحتمال، فإن العدد المتوقع للمقارنات هون+12{\displaystyle {\frac {n+1}{2}}}ومع ذلك، إذا عُلم أنها تحدث مرة واحدة، فإن الأمر يتطلب على الأكثر n − 1 مقارنة، ويكون العدد المتوقع للمقارنات هو

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

(على سبيل المثال، بالنسبة لـ n = 2، فإن هذا يساوي 1، وهو ما يتوافق مع بنية if-then-else واحدة).

في كلتا الحالتين، فإن أسوأ تكلفة في الحالة والتكلفة المتوقعة للبحث الخطي هما O ( n ).

احتمالات غير منتظمة

يتحسن أداء البحث الخطي إذا كان من المرجح أن تكون القيمة المطلوبة قريبة من بداية القائمة أكثر من نهايتها. لذا، إذا كانت بعض القيم أكثر عرضة للبحث من غيرها، فمن المستحسن وضعها في بداية القائمة.

على وجه الخصوص، عندما يتم ترتيب عناصر القائمة بترتيب تنازلي حسب الاحتمالية، وتكون هذه الاحتمالات موزعة هندسيًا ، فإن تكلفة البحث الخطي هي O(1) فقط. [ 6 ]

بشكل عام، إذا تم ترتيب العناصر بترتيب تنازلي حسب الاحتمالية، وكانت احتمالية البحث عن العنصر رقم i هيصأنا{\displaystyle p_{i}}، التكلفة المتوقعة لعملية بحث واحدة هيهـSياPتي=∑أنا=1نأناصأنا{\displaystyle ES^{OPT}=\sum _{i=1}^{n}ip_{i}}بافتراض أن الاحتمالات غير معروفة مسبقًا، أو أنه لا يمكن تخصيص الوقت لترتيب القائمة حسب الاحتمالات، يمكن استخدام أسلوب بنية البيانات ذاتية التعديل ، ونقل العناصر نحو بداية القائمة عند طلبها في عملية بحث. من بين الطرق الاستدلالية الطبيعية لهذا التعديل الذاتي، طريقتان: النقل إلى المقدمة (MF) والتبديل (T)، حيث يتبادل العنصر المطلوب مكانه مع العنصر السابق له. من المعروف أن التكلفة المتوقعة للوصول في سلسلة طويلة من عمليات الوصول المستقلة، محسوبة كمعدل على جميع الترتيبات الأولية للقائمة، تحقق الشرط التالي:هـSتي≤هـSمF≤π2هـSياPتي{\displaystyle ES^{T}\leq ES^{MF}\leq {\frac {\pi }{2}}ES^{OPT}}من حيث التكلفة المستهلكة ، وبأخذ المتوسط ​​على أسوأ سلسلة من العمليات (لاحظ - بين السلاسل التي تحقق افتراض الاحتمالات)، لديناSمF≤2SياPتي{\displaystyle S^{MF}\leq 2S^{OPT}}، بينماSتي{\displaystyle S^{T}}قد يكون الأمر سيئاً مثليا(مSياPتي){\displaystyle O(mS^{OPT})}[ 7 ]​

طلب

عادة ما يكون البحث الخطي بسيطًا جدًا في التنفيذ، وهو عملي عندما تحتوي القائمة على عدد قليل من العناصر، أو عند إجراء بحث واحد في قائمة غير مرتبة.

عند الحاجة إلى البحث عن قيم متعددة في قائمة واحدة، يُفضّل غالبًا معالجة القائمة مسبقًا لاستخدام طريقة أسرع. على سبيل المثال، يمكن فرز القائمة واستخدام البحث الثنائي ، أو بناء بنية بيانات بحث فعّالة منها. أما إذا كان محتوى القائمة يتغير باستمرار، فقد تُصبح إعادة تنظيمها بشكل متكرر أكثر إرهاقًا من جدواها.

ونتيجةً لذلك، فعلى الرغم من أن خوارزميات البحث الأخرى قد تكون أسرع من البحث الخطي نظريًا (مثل البحث الثنائي )، إلا أنه عمليًا، حتى مع المصفوفات متوسطة الحجم (حوالي 100 عنصر أو أقل)، قد يكون من غير العملي استخدام أي خوارزمية أخرى. أما مع المصفوفات الأكبر حجمًا، فلا جدوى من استخدام طرق بحث أخرى أسرع إلا إذا كانت البيانات كبيرة بما يكفي، لأن الوقت الأولي اللازم لإعداد (فرز) البيانات يُقارن بالوقت اللازم للعديد من عمليات البحث الخطي. [ 8 ]

انظر أيضاً

مراجع

الاقتباسات

  1. 1 2 Knuth 1998 ، §6.1 ("البحث التسلسلي").
  2. ↑ كنوت 1998 ، §6.2 ("البحث عن طريق مقارنة المفاتيح").
  3. ↑ Knuth 1998 ، §6.1 ("البحث التسلسلي")، القسم الفرعي "الخوارزمية ب".
  4. ↑ Knuth 1998 ، §6.1 ("البحث التسلسلي")، القسم الفرعي "الخوارزمية Q".
  5. ↑ Knuth 1998 ، §6.1 ("البحث التسلسلي")، القسم الفرعي "الخوارزمية T".
  6. ↑ كنوت، دونالد (1997). "القسم 6.1: البحث التسلسلي". الفرز والبحث . فن برمجة الحاسوب. المجلد 3 ( الطبعة الثالثة). أديسون-ويسلي. الصفحات 396-408 . ISBN    0-201-89685-0.
  7. ↑ بايزا-ياتس، ريكاردو؛ بوبليت، باتريسيو ف. (1999). "الفصل 2: ​​البحث". في عطا الله (محرر). دليل الخوارزميات ونظرية الحوسبة . مطبعة سي آر سي. ص 2-3 . ISBN  0849326494.
  8. ↑ هورفاث، آدم. "أداء البحث الثنائي والبحث الخطي على منصة .NET و Mono" . تم الاطلاع عليه بتاريخ 19 أبريل 2013 .

أعمال