0:00
[ЗАСТАВКА] Для оценки
сложности алгоритмов информатики используют такое понятие, как O.
Оно изображается, как большое O.
O используется для асимптотической оценки сложности функций,
и его можно интерпретировать,
как «эта функция растёт примерно так же, как аргумент O функции».
Например, O(N²) — это такие
алгоритмы, которые работают квадратично.
То есть если ваши данные увеличиваются в два раза,
то время работы увеличивается в 4 раза.
Если ваши данные увеличиваются в 10 раз, то время работы увеличивается в 100 раз.
И если данные и размер входных данных растёт очень быстро, то такие алгоритмы
становятся всё менее и менее эффективными и всё дольше и дольше читаются,
вплоть до невозможного времени, чтобы дождаться завершения этих алгоритмов.
Хорошие алгоритмы обычно линейны, то есть O(N).
И, если у вас в 2 раза больше данных, они занимают...
их вычисление занимает в 2 раза больше времени.
Если у вас в 10 раз больше данных, то нужно в 10 раз больше времени.
Бывают и другие оценки сложности.
Многие сортировки, например, работают за
N log (N), это хуже, чем N², но лучше, чем N.
Например, можно достаточно быстро,
примерно за 1 секунду, отсортировать 100 000 чисел.
Но миллиард чисел уже за одну секунду не отсортировать,
это нужно ждать намного дольше.
В то время как алгоритмы со сложностью O(N) для миллиарда работают за 1 секунду.
Также некоторые алгоритмы работают экспоненциальное время.
Это очень медленные и неэффективные алгоритмы,
но некоторые задачи могут решаться только такими алгоритмами.
Например, 2 в степени N если сложность вашего алгоритма,
то при росте N на единицу, то есть если у вас данных стало
чуть-чуть больше, время работы алгоритма увеличивается в 2 раза.
В частности, к таким задачам, которые решаются экспоненциальными алгоритмами,
относится задача разложения числа на простые множители.
И на этом держится вся криптография, и криптовалюты,
и защиты банковских систем в мире.
Из-за того, что эту задачу никто не знает, как решить эффективно,
все криптосистемы сложно взламывать и они взламываются за время,
которое больше существования всех банков и человечества.
Важно понимать, что при использовании нотации
O можно выкидывать незначащие небольшие значения,
которые находятся в функции, а также можно выкидывать константы.
То есть можно брать только мажорирующие элементы.
Например, если ваш алгоритм делает N² * 10
+ 3N операции, то всё равно можно сказать,
что он относится к классу квадратичных алгоритмов,
потому что класс скорее показывает, насколько растёт функция,
чем показывает конкретное время работы конкретного алгоритма для входных данных.
В частности, если у вас 10N², или 100N²,
это всё относится к классу O(N²).
И, несмотря на то, что реально алгоритмы могут работать, один в десять раз быстрее
другого, но асимптотически они одинаковы, то есть они растут примерно с одинаковой
скоростью и для достаточно больших N эта константа уже ничего не значит.
И всяко алгоритм, который работает за O(N) для больших N будет
намного более эффективен, чем O(N²),
даже если константа там в O(N) больше, чем в O(N²).
Такие обозначения вы будете встречать в статьях информатических,
в описаниях алгоритмов, и важно понимать,
что чем функция меньше, которая находится в O,
тем алгоритм лучше, быстрее выполняется, и лучше его применять.
Многие алгоритмы для информатики принадлежат классу O(N) просто потому,
что данных очень много, и некоторые задачи, которые возникают для информатики,
даже если они не решаются за линейное время, то создатели инструментов анализа
данных стараются придумать эвристики и разработать более эффективные алгоритмы,
которые работают линейно от данных, потому что когда у вас,
например, на вход подаётся сотни гигабайт ридов,
никакой квадратичный алгоритм просто не завершится за приемлемое время,
и лучше получить эвристический приблизительный результат,
чем ждать тысячу лет для того, чтобы получить точный результат.
Рассмотрим ещё один пример задачи нахождения позиции
рида в референсном геноме.
Например, у вас задан геном G,
который является строкой из букв A, C, G и T.
И таких букв может быть очень много.
Например, если вы ищете позицию рида в человеческом геноме,
то таких букв 3 миллиарда.
Три на десять в девятой.
Вам дан геном, нужно найти,
где встречается некоторый маленький фрагмент текста.
Эта задача называется «поиск подстроки в строке» или «поиск шаблона в тексте».
Допустим, у вас дан рид длины
100 пар оснований.
Чтобы найти его в геноме можно использовать очень простой алгоритм.
Попробовать посмотреть,
входит ли этот рид в геном в первой позиции,
то есть в самом начале, и сравнить каждые буквы попарно.
Для этого нужно сделать сто сравнений.
Если он не входит в первой позиции в наш геном,
то передвинуться во вторую позицию, проверить там, входит ли он.
Потом проверить в третьей позиции, в четвёртой позиции, и так далее.
Сколько операций нужно для того,
чтобы сравнить каждую букву из рида с каждой буквой,
с каждым нуклеотидом из генома?
Очевидно, что чтобы проверить одну позицию,
нужно сделать 100 операций сравнения.
Конечно, вы можете сказать, что в лучшем случае у нас уже первые буквы будут
неравны, и можно отбросить рассмотрение этой позиции и перейти дальше.
Да, некоторые ускорения можно здесь сделать,
но пока рассмотрим самый простой алгоритм, который сравнивает все буквы,
все сто букв из рида с конкретными буквами в геноме и
потом принимает решение: тут есть совпадение или тут нет совпадений.
Соответственно, чтобы проверить одну позицию, нужно сделать 100 операций.
Плюс нужно сделать 100 операций,
чтобы проверить вхождение рида во вторую позицию в геноме.
Дальше нужно сделать 100 операций, чтобы найти...
проверить вхождение рида в третью позицию генома, так далее,
и нужно сравнить, то есть проверить каждую позицию генома на вхождение этого рида.
Итого это будет примерно 100 умножить на количество всего
позиций в геноме, что достаточно долго.
На современном компьютере такая операция будет занимать
примерно 5 минут процессорного времени, то есть,
чтобы найти позицию одного рида в геноме, вам нужно подождать 5 минут.
Допустим, если у вас миллионы ридов, то вам нужно ждать очень,
очень долго, чтобы найти их выравнивание на геном.
Но для этой задачи существуют более эффективные алгоритмы,
о которых мы поговорим в следующей неделе,
которая будет как раз посвящена выравниванию коротких ридов на геномах.
Соответственно, от выбора правильного алгоритма для
решения конкретной задачи может зависеть очень многое.
В частности будет зависеть то,
дождётесь ли вы результата этой задачи или не дождётесь.
И если вы не дождётесь результатов выполнения этого алгоритма,
то все эти усилия были бессмысленны.
Соответственно вам нужно выбирать и правильные алгоритмы,
если вы разрабатываете новые инструменты в информатике, и уметь применять
подходящие алгоритмы, если вы применяете уже готовые инструменты,
которые написаны многими людьми в этой области.
[ЗАСТАВКА]
Alla L LapidusProfessor, Department of Cytology and Histology
Николай Вяххи
Павел ДобрынинМладший научный сотрудник
Михаил РайкоПостдок
Екатерина ЧерняеваПостдок
