4 года назад
Вычисление асимптотической сложности алгоритма Часть I. Основные понятия.
Нередко, читая описание какого либо алгоритма можно наткнуться на вычисление его асимптотической сложности, для новичка не всегда понятно что это такое. В данной статье мы дадим точное определение и разберем наиболее частые виды асимптотической сложности, а во второй части, которая выйдет завтра познакомимся с правилами ее вычисления. Асимптотическая сложность (производительность) алгоритма определяется функцией, которая указывает, насколько ухудшается работа алгоритма с усложнением поставленной задачи...
1239 читали · 2 года назад
Легко находим НОК или НОД с помощью алгоритма Евклида
Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления. Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3...