Vaqt murakkabligi
Eng yaxshi: O(n log log n)
O'rtacha: O(n log log n)
Eng yomon: O(n log log n)
Eratosfen elagi — n chegaragacha bo‘lgan barcha tub sonlarni topish uchun ishlatiladigan klassik algoritm. U 2 dan boshlab, har bir tub sonning karralilarini ketma-ket belgilash orqali ishlaydi.
Algoritm qanday ishlaydi:
1. 2 dan n gacha bo‘lgan sonlarni dastlab tub bo‘lishi mumkin deb belgilovchi mantiqiy massiv yaratish
2. 2 dan √n gacha bo‘lgan har bir i soni uchun, agar u hali ham tub deb belgilangan bo‘lsa, uning barcha karralilarini (i² dan boshlab) murakkab son sifatida belgilash
3. Sikl tugagach, belgilanib qolgan sonlar n dan katta bo‘lmagan tub sonlardir
Nima uchun o‘chirish i² dan boshlanadi?
i ning undan kichik barcha karralilari (2i, 3i, …, (i−1)i) allaqachon kichikroq tub sonlar tomonidan o‘chirilgan bo‘ladi.
Vaqt murakkabligi:
Eng yaxshi holat: O(n log log n)
O‘rtacha holat: O(n log log n)
Eng yomon holat: O(n log log n)
Xotira murakkabligi: O(n)
Xususiyatlari:
- Deterministik, tasodifiylikdan foydalanmaydi
- n xotiraga sig‘ganda keshdan samarali foydalanadi
- Sonlar nazariyasi va kriptografik ma’lumotlarni oldindan qayta ishlash uchun asosiy algoritmlardan biri
Algoritm qadimgi yunon matematigi Kirenalik Eratosfen (~miloddan avvalgi 276–194-yillar) sharafiga nomlangan. Ushbu elak kichik tub sonlarning barchasini topishning eng samarali usullaridan biri bo‘lib qolmoqda va ko‘plab faktorizatsiya jarayonlarida dastlabki qayta ishlash bosqichlari uchun asos bo‘lib xizmat qiladi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Eratosfen elagi (Sieve of Eratosthenes) nima?
- Eratosfen elagi — n chegaragacha bo‘lgan barcha tub sonlarni topish uchun ishlatiladigan klassik algoritm. U 2 dan boshlab, har bir tub sonning karralilarini ketma-ket belgilash orqali ishlaydi.
- Eratosfen elagi (Sieve of Eratosthenes) murakkabligi qanday?
- Vaqt (o'rtacha): O(n log log n) · Xotira: O(n)
- Ushbu Eratosfen elagi (Sieve of Eratosthenes) vizualizatori kimlar uchun?
- Eratosfen elagi (Sieve of Eratosthenes) vizualizatsiyasi "Matematika" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Eratosfen elagi (Sieve of Eratosthenes) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Matematika) quyidagilarni ko'rishingiz mumkin: Euclidean Algorithm. Har biri interaktiv vizualizatsiyaga ega.