Bitta o'tish algoritmi - One-pass algorithm

Bu maqola emas keltirish har qanday manbalar. Iltimos yordam bering ushbu maqolani yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Manbaga ega bo'lmagan materialga qarshi chiqish mumkin va olib tashlandi. Manbalarni toping: "Bitta o'tish algoritmi"  – Yangiliklar  · gazetalar  · kitoblar  · olim  · JSTOR (2007 yil yanvar) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Hisoblashda, a bitta o'tish algoritmi a oqim algoritmi uning kiritilishini aniq bir marta, tartibda, cheksiz o'qiydi buferlash. Odatda bitta o'tish algoritmi talab qiladi O(n) (qarang "katta O" belgisi ) vaqt va undan kam O(n) saqlash (odatda O(1)), qaerda n kirish kattaligi.

Asosan bitta o'tish algoritmi quyidagicha ishlaydi:

1. Ob'ekt tavsiflari ketma-ket ishlov beriladi
2. Birinchi ob'ekt birinchi klasterning klaster vakili bo'ladi
3. Har bir keyingi ob'ekt, ishlov berish vaqtida mavjud bo'lgan barcha klaster vakillariga mos keladi
4. Berilgan ob'ekt mos keladigan funktsiyadagi ba'zi bir shartlarga muvofiq bitta klasterga (yoki bir-biriga ko'proq yo'l qo'yilsa) beriladi
5. Ob'ekt klasterga berilganda, ushbu klaster uchun vakili qayta hisoblanadi
6. Agar ob'ekt ma'lum bir sinovdan o'ta olmasa, u yangi klasterning klaster vakili bo'lib qoladi, hech narsa sodir bo'lmaydi

Bir martalik algoritm bilan echiladigan misol masalalari

Kirish sifatida har qanday ro'yxat berilgan:

• Elementlar sonini hisoblang.

Raqamlar ro'yxati berilgan:

• Toping k eng katta yoki eng kichik elementlar, k oldindan berilgan.
• Toping sum, anglatadi, dispersiya va standart og'ish ro'yxat elementlaridan. Variantni hisoblash uchun algoritmlar

Alifbosidagi belgilar ro'yxati berilgan k oldindan berilgan belgilar.

• Kirishda har bir belgi necha marta paydo bo'lishini hisoblang.
• Eng tez-tez yoki kam uchraydigan elementlarni toping.
• Belgilar bo'yicha ba'zi tartiblarga ko'ra ro'yxatni saralash (belgilar soni cheklangan bo'lishi mumkin).
• Berilgan belgining ikkita ko'rinishi orasidagi maksimal bo'shliqni toping.

Bir martalik algoritm bilan hal qilinmaydigan misol muammolari

Kirish sifatida har qanday ro'yxat berilgan:

• Toping noxiridan element (yoki ro'yxat kamroq bo'lganligi haqida xabar bering n elementlar).
• Ro'yxatning o'rta elementini toping.

Raqamlar ro'yxati berilgan:

• Toping o'rtacha.
• Toping rejimlar (Bu cheklangan alifbodan eng tez-tez uchraydigan belgini topish bilan bir xil emas).
• Ro'yxatni saralash.