2021-02-21 08:00:21
Алгоритмы и структуры данных, которые должен знать каждый программист. Алгоритмы сортировки Сортировка - это наиболее изученная концепция в компьютерных науках. Идея состоит в том, чтобы расположить элементы списка в определенном порядке. Хотя каждый основной язык программирования имеет встроенные библиотеки сортировки, они пригодятся, если вы знаете, как они работают. В зависимости от требований вы можете использовать любой из них.
-Сортировка слиянием
-Быстрая сортировка
-Сортировка кучей
-Сортировка подсчётом
Что еще более важно, нужно знать, когда и где их использовать. Вот несколько примеров, в которых вы можете найти прямое применение методов сортировки:
-Сортировка по цене, популярности и т. Д. На сайтах электронной коммерции
Алгоритмы поиска Двоичный поиск (в линейных структурах данных)
Двоичный поиск используется для очень эффективного поиска в отсортированном наборе данных. Временная сложность O (log2N). Идея состоит в том, чтобы многократно разделить пополам часть списка, которая может содержать элемент, пока мы не сузим его до одного возможного элемента. Некоторые приложения:
Когда вы ищете название песни в отсортированном списке песен, он выполняет двоичный поиск и сопоставление строк, чтобы быстро вернуть результаты.
Используется для отладки в git через git bisect
Поиск в глубину / ширину (в структурах данных Graph)
Приложения:
-Используется поисковыми системами для веб-сканирования
-Используется в искусственном интеллекте для создания ботов, например шахматного бота.
-Поиск кратчайшего пути между двумя городами на карте и многие другие подобные приложения
regex и анализ строк Сопоставление / поиск по образцу - одна из самых важных проблем в компьютерных науках. По этой теме было проведено множество исследований, но мы укажем только два основных предмета, необходимых любому программисту.
Алгоритм KMP (сопоставление строк)
Алгоритм Кнута-Морриса-Пратта используется в тех случаях, когда нам нужно сопоставить короткий шаблон с длинной строкой. Например, когда мы Ctrl + F ключевое слово в документе, мы выполняем сопоставление с образцом во всем документе.
Регулярное выражение (анализ строк)
Часто нам приходится проверять строку, анализируя заранее заданное ограничение. Он широко используется в веб-разработке для синтаксического анализа и сопоставления URL-адресов.
Экспонентация Допустим, вы хотите вычислить 2 в 32 степени. Обычно мы выполняем итерацию 32 раза и находим результат. Что, если бы я сказал вам, что это можно сделать за 5 итераций?
Возведение в степень возведения в квадрат или возведение в степень двоичного возведения в степень - это общий метод быстрого вычисления больших положительных целых степеней числа в O (log2N). Мало того, этот метод также используется для вычисления степеней многочленов и квадратных матриц.
Пример использования:
Вычисление больших степеней числа чаще всего требуется при шифровании RSA. RSA также использует модульную арифметику наряду с двоичным возведением в степень.
2.9K views05:00
![Логотип телеграм канала @frontendnoteschannel — Frontender's notes [ru]](https://logos.telegram-store.com/channels/frontendnoteschannel/telegram_logo.jpg){kind=logo}
F
