@notxxx1 - админ
@Golang_google - Golang для разработчиков
@itchannels_telegram - 🔥лучшие из ит
@golangl - chat
@golangtests - golang tests
@golang_jobsgo - go chat jobs
@ai_machinelearning_big_data - AI
@data_analysis_ml
РКН: clck.ru/3FmtKd
Post #1553
3.8K
🧠 Алгоритм Флойда знают многие Go-разработчики: два указателя двигаются с разной скоростью и находят цикл в связном списке за `O(n)` времени и `O(1)` памяти.
Но есть менее известный алгоритм Брента, который решает ту же задачу и часто делает меньше переходов по
Флойд:
Брент работает иначе: один указатель движется постоянно, а второй используется как контрольная точка. Размер интервала постепенно удваивается:
Асимптотика та же:
Но Брент обычно делает меньше обращений к следующему элементу списка. Если
Флойда спрашивают на собеседованиях постоянно. Про Брента многие Go-разработчики вообще не слышали.
Но есть менее известный алгоритм Брента, который решает ту же задачу и часто делает меньше переходов по
Next.Флойд:
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
Брент работает иначе: один указатель движется постоянно, а второй используется как контрольная точка. Размер интервала постепенно удваивается:
1 → 2 → 4 → 8 → 16
power, lam := 1, 1
tortoise := head
hare := head.Next
for hare != nil && tortoise != hare {
if power == lam {
tortoise = hare
power *= 2
lam = 0
}
hare = hare.Next
lam++
}
Асимптотика та же:
O(n) по времениO(1) по памятиНо Брент обычно делает меньше обращений к следующему элементу списка. Если
Next вычисляется дорого или данные читаются через сложную структуру, разница уже может быть заметной.Флойда спрашивают на собеседованиях постоянно. Про Брента многие Go-разработчики вообще не слышали.
- ❤ 16
- 🤔 5
- 👍 3
- 🥰 1
