[ЗАСТАВКА] Для оценки сложности алгоритмов информатики используют такое понятие, как 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 минут. Допустим, если у вас миллионы ридов, то вам нужно ждать очень, очень долго, чтобы найти их выравнивание на геном. Но для этой задачи существуют более эффективные алгоритмы, о которых мы поговорим в следующей неделе, которая будет как раз посвящена выравниванию коротких ридов на геномах. Соответственно, от выбора правильного алгоритма для решения конкретной задачи может зависеть очень многое. В частности будет зависеть то, дождётесь ли вы результата этой задачи или не дождётесь. И если вы не дождётесь результатов выполнения этого алгоритма, то все эти усилия были бессмысленны. Соответственно вам нужно выбирать и правильные алгоритмы, если вы разрабатываете новые инструменты в информатике, и уметь применять подходящие алгоритмы, если вы применяете уже готовые инструменты, которые написаны многими людьми в этой области. [ЗАСТАВКА]
