Это статья об основах программирования на Go. На канале я рассказываю об опыте перехода в IT с нуля, структурирую информацию и делюсь мнением.
Хой, джедаи и амазонки!
Решал контест от Яндекса и не выполнил ни одной задачи. Понял, что нужна подготовка по алгоритмам. В плане оформить серию публикаций, где буду осваивать алгоритмы и показывать примеры решённых задач на LeetCode.
Разберёмся сперва с термином алгоритм, далее пройдёмся по одному из самых известных алгоритмов, посмотрим на время выполнения алгоритмов и порешаем задачи с LeetCode.
Алгоритм - последовательность инструкций для решения задачи. Одну задачу можно решить разными алгоритмами, у каждого их которых есть плюсы и минусы. Но в целом есть алгоритмы эффективные и "в лоб", т.е. - неэффективные.
1. Бинарный поиск
Бинарный поиск - алгоритм, который на входе получает элемент для поиска и отсортированный список существующих элементов для поиска, а на выходе выдаёт позицию искомого элемента в существующем списке.
Если в словаре 500 000 слов, простым перебором (линейным поиском) в худшем сценарии нам нужно проверить 500 000 слов, прежде чем найти нужное слово. При бинарном поиске число шагов в худшем случае определяется формулой логарифм n по основанию два:
Т.е. для 500 000 отсортированных слов нужно всего 19 шагов.
Суть бинарного поиска постоянно делить существующий список элементов на два и сравнивать найденный средний элемент списка с искомым. В зависимости, больше искомый элемент среднего элемента или меньше, продолжить поиск в "правой" или "левой" части существующего списка элементов.
Бинарным он называется, поскольку каждый раз рассматривается одна из двух возможных половин существующего списка данных. Это отличает его от линейного поиска, где каждый элемент последовательно проверяется.
При бинарном поиске за каждую операцию исключается половина возможных элементов.
В стандартной библиотеке бинарный поиск реализован так:
А вот пример кода для её вызова:
Функция Search принимает длину массива arr и анонимную функцию, которая определяет, считается ли элемент в массиве меньшим, равным или большим искомого элемента. После выполнения поиска мы анализируем результат, чтобы определить, был ли найден элемент, и выводим соответствующее сообщение.
--------------------------------------------
Напишем свою функцию, чтобы она принимала массив и элемент для поиска:
Функция checkBinary возвращает позицию искомого значения в заданном массиве, либо возвращает -1, если искомого значения в массиве нет.
И доработаем функцию main:
Мы реализовали функцию бинарного поиска. Код на GitHub.
2. Время выполнения алгоритма
Когда для выполнения задачи нужно проверить каждый элемент существующих данных - это линейное время.
Бинарный поиск выполняется за логарифмическое время.
При увеличении числа исходных элементов, время работы бинарного поиска увеличивается незначительно, а линейного - пропорционально увеличению входных данных. Как оценить это время?
2.1. О-большое
Нотация О() описывает время работы алгоритма в худшем случае. Используется для оценки роста времени выполнения алгоритма или потребляемой памяти в зависимости от входных данных. Таким образом, О-большое применяют:
- О() для оценки времени
- О() для оценки памяти.
Для одного алгоритма оценка по времени и памяти может быть одинаковой, а может быть разной. Чаще - второй случай.
Пока поговорим об О-большом, применительно ко времени. О-большое не оценивает время в секундах или часах, О-большое оценивает количество необходимых шагов для решения задачи.
Примеры распространённых О-больших:
- О(1) - постоянное время. Пример - поиск в хеш-таблице.
- О(log n) - логарифмическое время. Пример - бинарный поиск.
- О(n) - линейное время. Пример - поиск перебором.
- О(n * log n). Линейно-логарифмическая сложность. Пример: эффективные алгоритмы сортировки.
- О(log n^2). Квадратичная скорость. Пример: медленные алгоритмы сортировки (сортировка выбором).
- О(n!). Факториальная скорость. Пример: очень медленные алгоритмы (задача о коммивояжере).
Итак, основное - время выполнения алгоритма описывается ростом операций и выражается как "О-большое" и не измеряется в секундах, минутах или часах.
3. LeetCode
Я не подбираю каких-то особых задач, связанных с бинарным поиском. Просто несложные задачи и способы их решения. Решения сейчас занимают много времени, т.к. пока не освоил теорию как решать типовые алогоритмы.
3.1. Палиндром.
Проверить, является ли число палиндромом. Т.е. если его перевернуть, то оно будет таким же. Например, палиндромом будет 191, 2332. Ссылка на литкод.
Вот как можно реализовать функцию:
3.2. Римские цифры
Нужно конвертировать число, записанное римскими цифрами в число, записанное арабскими цифрами. Код задачи на литкоде. Тут штука в чём - на литкоде задание описано криво, нужно было найти нормальное объяснение, как формируются числа римскими цифрами.
Решение на GitHub.
3.3. Поиск самого частого символа в строке
Задана строка, нужно найти какой символ чаще всего в ней встречается.
Решение на GitHub.
Вообще, карты как я понял, часто используются для решения алгоритмических задач благодаря своим свойствам замены повторяющегося ключа или быстрому поиску информации в них.
4. Итоги
Этой публикацией запускаю серию статей, посвящённых алгоритмам. Рассчитываю вырасти в этой сфере и одновременно тренироваться в решении несложных бизнес-задач, чтобы найти работу и когда на неё устроюсь, чувствовать себя увереннее благодаря наработанному опыту.
Благодарю, что дочитали эту публикацию до конца. Успехов! Будем на связи.
Бро, ты уже здесь? 👉 Подпишись на канал для новичков «Войти в IT» в Telegram, будем изучать IT вместе 👨💻👩💻👨💻