Как эффективно определяешь временную сложность алгоритмов
Большинство из тех, кто связан с IT, слышали о понятии временной сложности алгоритмов. Однако её оценка для конкретных случаев с трудом даётся кандидатам на собеседованиях. Вот всё, что нужно, чтобы начать эффективно в ней ориентироваться:
🔸 O(1) – константная сложность.
Это значит, что операция выполняется за фиксированное время, вне зависимости от размера входных данных. Например, присвоение значения переменной выполняется за константное время. Или извлечение значения из массива по индексу.
🔸 O(log(n)) – логарифмическая
Сюда попадают алгоритмы, которые с каждой следующей итерацией работы делят набор входных данных пополам. Такая сложность чаще всего встречается при работе с древовидными структурами данных.
🔸 O(n) – линейная
Тесно связана с количеством проходов по массиву данных. Иначе говоря, совпадает с количеством вложенных циклов. Если алгоритм отрабатывает за один проход по массиву – это O(n). Если перед нами цикл в цикле – O(n^2). И так далее.
🔸 O(n log(n)) – линейно-логарифмическая
Типичный представитель сложности для «хороших» сортировок, используемых на практике. Например quicksort или mergesort.
---
Для эффективной оптимизации своего кода на основе временной сложности, нужно понимать, как устроены алгоритмы и структуры данных.
Поэтому рекомендую книгу «Алгоритмы. Руководство по разработке. 3-е изд» Стивена Скиены. Первая её половина содержит исчерпывающую информацию об алгоритмах и структурах данных. Вторая – является справочником по решению типовых задач.
А вот вам пара дополнительных полезных ссылок:
bigocheatsheet.com – шпаргалка по временным сложностям популярных структур данных.
visualgo.net – аналогичная шпаргалка по алгоритмам. Включает в себя наглядные визуализации работы алгоритмов и теорию к ним.
Большинство из тех, кто связан с IT, слышали о понятии временной сложности алгоритмов. Однако её оценка для конкретных случаев с трудом даётся кандидатам на собеседованиях. Вот всё, что нужно, чтобы начать эффективно в ней ориентироваться:
🔸 O(1) – константная сложность.
Это значит, что операция выполняется за фиксированное время, вне зависимости от размера входных данных. Например, присвоение значения переменной выполняется за константное время. Или извлечение значения из массива по индексу.
🔸 O(log(n)) – логарифмическая
Сюда попадают алгоритмы, которые с каждой следующей итерацией работы делят набор входных данных пополам. Такая сложность чаще всего встречается при работе с древовидными структурами данных.
🔸 O(n) – линейная
Тесно связана с количеством проходов по массиву данных. Иначе говоря, совпадает с количеством вложенных циклов. Если алгоритм отрабатывает за один проход по массиву – это O(n). Если перед нами цикл в цикле – O(n^2). И так далее.
🔸 O(n log(n)) – линейно-логарифмическая
Типичный представитель сложности для «хороших» сортировок, используемых на практике. Например quicksort или mergesort.
---
Для эффективной оптимизации своего кода на основе временной сложности, нужно понимать, как устроены алгоритмы и структуры данных.
Поэтому рекомендую книгу «Алгоритмы. Руководство по разработке. 3-е изд» Стивена Скиены. Первая её половина содержит исчерпывающую информацию об алгоритмах и структурах данных. Вторая – является справочником по решению типовых задач.
А вот вам пара дополнительных полезных ссылок:
bigocheatsheet.com – шпаргалка по временным сложностям популярных структур данных.
visualgo.net – аналогичная шпаргалка по алгоритмам. Включает в себя наглядные визуализации работы алгоритмов и теорию к ним.