النظرية الرئيسة (تحليل الخوارزميات)

في تحليل الخوارزميات، تُقدم النظرية الرئيسة لتواترات فرق تسد (بالإنجليزية: master theorem for divide-and-conquer recurrences)‏ تحليلاً تقاربياً (باستخدام ترميز أوه الكبير) للعلاقات التواترية التي تحدث في الكثير من خوارزميات فرق تسد. تم طرح هذه الطريقة لأول مرة في عام 1980م من قبل جون بنتلي، ودوروثيا بلوستاين، وجيمس بنجامين ساكس. ووُصفت على أنها طريقة موحدة لحل تواترات معينة.[1] روج اسم هذه الطريقة (النظرية الرئيسة) كتاب مقدمة في الخوارزميات. لا يمكن حل جميع التواترات بهذه النظرية؛ وتوفر طريقة أكرا-بزي تعميماً أكبر.

مراجع
  1. Bentley, Jon Louis; Haken, Dorothea; Saxe, James B. (September 1980), "A general method for solving divide-and-conquer recurrences", ACM SIGACT News, 12 (3): 36–44, doi:10.1145/1008861.1008865, مؤرشف من الأصل (PDF) في 22 سبتمبر 2017 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
    • بوابة علم الحاسوب
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.