Алгоритм — любая корректно определенная вычислительная процедура, на вход (input) которой подаются значения и результатом выполнения которой являются выходные (output) данные
Алгоритм — последовательность вычислительных шагов, преобразующих входные величины в выходные
Часто возникает необходимость в сортировке (эта хуета будет тебя преследовать до конца жизни) ⇒ существует много алгоритмов для разных случаев сортировки (да и не только сортировки, а вообще любой задачи, решаемой с помощью алгоритмов)
Структура данных - способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию. Тут тоже ремарочка, что все структуры данных по-своему хороши и плохи
Алгоритмы имеют два основных критерия: память и время исполнения. На деле обе эти шняги - ценный ограниченный ресурс (производительность и память компа требуют денежек и железяк-схем-микросхем-ядер), поэтому хороший алгоритм должен подходить под определенную задачу по этим двум критериям.
Оценку алгоритма по памяти и времени называют асимптотической оценкой или же просто асимптотикой.
Как уже было сказано выше, каждый алгоритм можно оценить по нескольким критериям. Для нас важнее всего - время исполнения и память, требуемая алгоритму.
Асимптотику можно посчитать. А если точнее, описать её функцией, которая будет говорить о том, насколько эффективна программа в разных случаях. Особенно хорошо это будет видно на асимптотике графов в 2 семестре: там она напрямую зависит от количества вершин и рёбер графа.
Пример временной оценки: Существует самая наивная сортировка вставкой, которая работает за c1n², где c1 - константа, зависящая от мощности компа (условно), а n - количество элементов, которые нужно отсортировать. Также существует сортировка слиянием (merge sort), временная сложность которой - c2n*log(n), где c2 - другая константа с другой мощностью компа, n - количество элементов.
Важно то, что константы (ака мощности компа) не настолько важны, как “мощность” самого алгоритма, даже если c1 < c2 (с1 мощнее с2).
Ещё интереснее то, что сортировка вставкой будет работать быстрее мёрджсорта, но на маленьких размерах сортируемого массива. При каком-то значении n мёрджсорт будет в разы эффективнее сортировки вставками (легко проверить просто подставив разные n в асимптотики). Общее правила таково: чем больше количество сортируемых элементов, тем заметнее преимущество сортировки слиянием