Ivan Petrushenko

Half the easy/medium задач на масивах на співбесідах розв'язується одним прийомом: тримаємо два індекси і рухаємо їх залежно від порівняння. Ключова властивість — кожен вказівник монотонний: він рухається лише в один бік і ніколи не повертається. Тому сумарна кількість кроків обмежена довжиною масиву — і наївний вкладений цикл за O(n²) перетворюється на один прохід за O(n). «Два вказівники» — це насправді парасолька над кількома різними патернами. Їх легко сплутати, бо всі тримають два...

Рекурсія — це насправді дві ідеї, які випадково мають одну назву. З погляду алгоритмів це стратегія: звести задачу до меншої версії тієї самої задачі, розв'язати меншу — і зібрати відповідь. Так працюють divide-and-conquer алгоритми: mergesort, quicksort, обхід дерев. З погляду коду це просто функція, яка викликає сама себе. Обидва погляди описують те саме з різних боків: рекурсивна функція — це рекурсивний алгоритм, записаний у коді. У цій статті розберемо, з чого складається будь-яка...

Коли є два алгоритми, що розв'язують одну задачу, хочеться заздалегідь знати, який із них швидший — ще до того, як писати код. Саме для цього існує асимптотичний аналіз і нотація Big O (O велике). У цій статті розберемо, як рахувати складність алгоритмів, що означають записи на кшталт O(n), O(log n) чи O(n²), і як аналізувати цикли та рекурсію на конкретних прикладах. Навіщо взагалі оцінювати час роботи алгоритму Здавалося б, можна просто запустити код і заміряти час. Але з цим є проблеми: на...