خوارزمية المرور الواحد

في مجال الحوسبة، تُعرف خوارزمية المرور الواحد بأنها خوارزمية تدفق تقرأ مدخلاتها مرة واحدة فقط. ^{[ 1 ]} وتقوم بذلك عن طريق معالجة العناصر بالتسلسل، دون تخزين مؤقت غير محدود ؛ حيث تقرأ كتلة في مخزن مؤقت للإدخال ، ثم تعالجها، وتنقل النتيجة إلى مخزن مؤقت للإخراج لكل خطوة في العملية. ^{[ 2 ]} تتطلب خوارزمية المرور الواحد عمومًا زمنًا قدره O ( n ) (انظر ترميز "Big O" ) ومساحة تخزين أقل من O ( n ) (عادةً O (1))، حيث n هو حجم المدخلات. ^{[ 3 ]} ومن أمثلة خوارزمية المرور الواحد عملية اتخاذ القرار ماركوف القابلة للملاحظة جزئيًا من نوع Sondik . ^{[ 4 ]}

بافتراض وجود أي قائمة كمدخل:

• احسب عدد العناصر.

بافتراض وجود قائمة من الأرقام:

• أوجد أكبر أو أصغر k عنصر، حيث k معطاة مسبقاً.
• أوجد مجموع ومتوسط ​​وتباين وانحراف معياري عناصر القائمة. انظر أيضًا خوارزميات حساب التباين .

بافتراض وجود قائمة من الرموز من أبجدية مكونة من k رمزًا، معطاة مسبقًا.

• احسب عدد مرات ظهور كل رمز في المدخلات.
• ابحث عن العناصر الأكثر تكراراً أو الأقل تكراراً.
• قم بترتيب القائمة وفقًا لترتيب معين للرموز (ممكن نظرًا لأن عدد الرموز بعد "و" محدود).
• أوجد أقصى فارق زمني بين ظهورين متتاليين لرمز معين.

بافتراض وجود أي قائمة كمدخل:

• ابحث عن العنصر رقم n من النهاية (أو أبلغ أن القائمة تحتوي على أقل من n عنصر).
• ابحث عن العنصر الأوسط في القائمة. ومع ذلك، يمكن حل هذه المسألة على مرحلتين: المرحلة الأولى تحسب العناصر، والمرحلة الثانية تختار العنصر الأوسط.

بافتراض وجود قائمة من الأرقام:

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

الخوارزميات ذات المرورين المذكورة أعلاه لا تزال خوارزميات تدفق البيانات ولكنها ليست خوارزميات ذات مرور واحد.