Yevklid algoritmi murakkabligi qanday?

Vaqt (o'rtacha): O(log min(a, b)) · Xotira: O(1)

Ushbu Yevklid algoritmi vizualizatori kimlar uchun?

Yevklid algoritmi vizualizatsiyasi "Matematika" kategoriyasida boshlang'ich darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.

Yevklid algoritmi ga o'xshash qanday algoritmlar bor?

Shu kategoriyada (Matematika) quyidagilarni ko'rishingiz mumkin: Sieve of Eratosthenes. Har biri interaktiv vizualizatsiyaga ega.

Yevklid algoritmi — Algoritmlar vizualizatori

Vaqt murakkabligi

Eng yaxshi: O(1)

O'rtacha: O(log min(a, b))

Eng yomon: O(log min(a, b))

Yevklid algoritmi ikkita butun sonning eng katta umumiy bo‘luvchisini (EKUB) hisoblaydi — bu ikkala sonni ham qoldiqsiz bo‘ladigan eng katta sondir. U hozirgacha keng qo‘llaniladigan eng qadimgi algoritmlardan biridir.

Asosiy g‘oya: a va b sonlarining ikkalasini ham bo‘ladigan har qanday son a mod b qoldig‘ini ham bo‘ladi. Shuning uchun gcd(a, b) = gcd(b, a mod b). Bu amalni takrorlash orqali sonlar juftligi kichrayib boradi va oxir-oqibat qoldiq 0 ga teng bo‘ladi.

Qanday ishlaydi:

1. a ni b ga bo‘lib, r = a mod b qoldig‘ini olish

2. Agar r 0 ga teng bo‘lsa, javob b bo‘ladi

3. Aks holda, sonlar juftligini (b, r) bilan almashtirish va takrorlash

Nima uchun tez ishlaydi:

Qoldiq har ikki qadamda kamida ikki baravar kamayadi. Shu sababli bo‘lishlar soni O(log min(a, b)) ga teng bo‘ladi — bu barcha mumkin bo‘lgan bo‘luvchilarni birma-bir tekshirishdan ancha tez.

Vaqt murakkabligi:

Eng yaxshi: O(1)

O‘rtacha: O(log min(a, b))

Eng yomon: O(log min(a, b))

Xotira murakkabligi: iterativ versiya uchun O(1)

Xususiyatlari:

Deterministik, tasodifiylikdan foydalanmaydi
Faqat modul bo‘yicha qoldiq olish amalidan foydalanadi — faktorizatsiya talab qilinmaydi
Kengaytirilgan Yevklid algoritmi, modul bo‘yicha teskari elementlarni topish va kasrlarni qisqartirish uchun asos bo‘ladi

Yunon matematigi Yevklid tomonidan o‘zining «Negizlar» asarida (~miloddan avvalgi 300-yil) bayon etilgan ushbu algoritm hozirgi kunda ham zamonaviy arifmetika, kriptografiya (RSA kalitlari matematikasi) va kompyuter algebra tizimlarining muhim asoslaridan biri hisoblanadi.

O'xshash algoritmlar

Sieve of Eratosthenes

Ko'p beriladigan savollar

Yevklid algoritmi nima?: Yevklid algoritmi ikkita butun sonning eng katta umumiy bo‘luvchisini (EKUB) hisoblaydi — bu ikkala sonni ham qoldiqsiz bo‘ladigan eng katta sondir. U hozirgacha keng qo‘llaniladigan eng qadimgi algoritmlardan biridir.
Yevklid algoritmi murakkabligi qanday?: Vaqt (o'rtacha): O(log min(a, b)) · Xotira: O(1)
Ushbu Yevklid algoritmi vizualizatori kimlar uchun?: Yevklid algoritmi vizualizatsiyasi "Matematika" kategoriyasida boshlang'ich darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
Yevklid algoritmi ga o'xshash qanday algoritmlar bor?: Shu kategoriyada (Matematika) quyidagilarni ko'rishingiz mumkin: Sieve of Eratosthenes. Har biri interaktiv vizualizatsiyaga ega.