Часть 0.1. Поясняю за структуры данных (часть 1)⁠⁠

Привет, меня зовут Артем и я люблю программировать. Надеюсь, вы прочитали предыдущую, нулевую статью.

Что бы стать хорошим программистом (не веб-разработчиком, а хорошим программистом), вы в первую очередь должны понять, что программирование – это манипуляция данными. И то, насколько вы хорошо умеете обращаться с данными в зависимости от поставленной задачи, определяет, сможете ли вы создавать хорошие программы или нет. В интернете уже есть куча материала на тему структур данных и алгоритмов, но я попробую расписать весь этот материал по-своему. Возможно, это поможет кому-то лучше понять эту тему.

Начнем с определения понятия «сложность алгоритма» — это нам пригодится тут и в следующей статье про алгоритмы.

Если говорить простыми словами – то сложность алгоритма – это то, сколько действий нужно совершить данному алгоритму, чтобы выполнить определенную задачу. Чем больше действий нужно алгоритму, тем он сложнее, и тем он хуже (если существуют альтернативные алгоритмы с меньшей сложностью).

Например, представим ряд чисел – 12345. Нам нужно инвертировать порядок этих чисел (переставить числа так, чтобы вышло 54321). Представим, что алгоритму №1 нужно совершить 5 действий, чтобы переставить числа, а алгоритму №2 – 10. Из этого можем сделать вывод, что в данном случае алгоритм №1 будет предпочтительней для нас.

Но это говоря простыми словами. В реальности на выбор алгоритма также влияет то, сколько памяти он занимает в процессе работы (например, у алгоритма высокая сложность, но он кушает мало памяти, и для устройств с малым количеством оперативной памяти лучше реализовать его), сложность реализации алгоритма (например, мы знаем, что алгоритм «быстрой сортировки» быстрее, чем алгоритм «сортировки пузырьком». Но у вас в компании работают только веб-программисты, которые написать алгоритм быстрой сортировки не смогут. Поэтому вам ничего не остается, кроме реализации алгоритма «сортировки пузырьком») и требования алгоритма к железу (в основном это алгоритмы для нейросетей, которые работают на видеокартах. Например, что бы прогнать картинку 512х512 пикселей через нейросеть типа ESRGAN, вам потребуется видеокарта, у которой не менее 2 ГБ видеопамяти).

Сложность алгоритма обозначается большим О. Например, O(1), O(n), O(n!). И тут все сложна легко. Вспоминаем математику, на которой ты стрелял в друга скомканными шариками из ручки, что значение функции может зависеть (или не зависеть) от определенных параметров этой функции. Например, функция 1 = n (это то же самое, что и O(1)) говорит, что независимо от значения n результат всегда будет 1. Функция y = n! (это O(n!)) означает, что результат (это y) будет равняться значение n факториал (не путать с фракталом). То есть, если у нас 5 чисел, то алгоритм сложностью O(n!) сделает 1 * 2 * 3 * 4 * 5 операций (посчитай сам, сколько это).

Лично мне нравиться эта табличка, которую я нашел в группе /dev/null в ВК

Другой взгляд на О большое:

O(1) = O(уууее)

O(log n) = O(да)

O(n) = O(к)

O(n^2) = O(йблин)

O(2^n) = O(нет)

O(n!) = O(МГ!)

Как это связано со структурами данных? Структуры данных и алгоритмы очень тесно связаны, и у каждой структуры есть свои алгоритмы обхода элементов структуры, их добавление\удаление, поиск в структуре и т.д. И поэтому важно знать сложность алгоритмов, которые дают нам возможность управлять этой структурой, что бы выбрать подходящую для решения нашей задачи.

Со сложностью алгоритмов вроде разобрались. На практике для каждой задачи есть несколько решений, и вы сами, как программист, вольны выбрать то, которое подходит именно под вашу ситуацию.

В следующей статье я попробую рассказать о структурах данных, зачем они нужны и рассмотреть такие структуры, как стек, очередь и связанный список.

После прочтения данного текста можете заглянуть в комментарии - там могут дополнить материал или исправить ошибки в данном материале.