Курс «Сложность алгоритмов» от Школы Анализа Данных.
Каждый алгоритм обладает таким понятием как сложность, причем сложности у алгоритма могут быть разные. Почитать введение по теме можно в нашей статье: https://tproger.ru/translations/algorithms-and-data-structures/
А чтобы совсем хорошо разобраться в теме, рекомендуем посмотреть видеокурс ШАДа, записи лекций которого мы собрали в этом посте:
1. Машины Тьюринга и арифметические алгоритмы.
2. Теорема об иерархии. Сведение задач друг к другу.
3. Класс NP. Сведение задач друг к другу.
4. Теорема Кука-Левина. Доказательства NP полноты.
5. Приближенное решение задач оптимизации.
6. #P полные задачи. Сведения задач подсчета друг к другу.
7. PSpace полные задачи. Определение вычислительной сложности проблем.
8. Вероятностные алгоритмы. Схемная сложность.
9. Интерактивные доказательства. Схемная сложность.
10. Доказательства с нулевым разглашением. Односторонние функции.
Остальные лекции можно посмотреть в плейлисте: https://vk.cc/6iigpT
#algo@tproger #video@tproger