Здравствуйте, я Косуке Кузуока, инженер-исследователь в области искусственного интеллекта в DeNA Co., Ltd. Недавно у меня была возможность пересмотреть структуры данных и алгоритмы, и я подумал, что сейчас хорошее время, чтобы поделиться своими знаниями и реализацией, написанной на python. .
Я пишу серию сообщений в блоге, охватывающих темы от основ структур данных и алгоритмов до передовых компьютерных наук. Это сообщение в блоге предназначено для новичков или людей, которые хотят изучить основы темы CS. Весь код, используемый в этой серии, находится в этом репозитории Github. Давайте нырнем!
ОБНОВЛЕНО: Прошло много времени с тех пор, как я начал эту серию сообщений в блоге. Я много работал над этой серией и каждую неделю публикую новый пост! Вот все ссылки на публикации, опубликованные на данный момент в этой серии. Наслаждайтесь 😎
- Часть 1: Что такое структуры данных и алгоритмы? *
- Часть 2: Наиболее широко используемые структуры данных (массивы и связанные списки)
- Часть 3: Наиболее широко используемые структуры данных (стеки и очереди)
- Часть 4: Поиск и сортировка (двоичный поиск)
- Часть 5: Поиск и сортировка (рекурсия и DP)
Что такое структуры данных?
Короче говоря, структуры данных - это способы хранения данных на вашем компьютере. Я предполагаю, что вы знаете о массивах и списках. Массив - это структура данных, в которой может храниться большой объем данных. С массивами можно делать много чего, но у массивов есть и недостатки. В некоторых случаях лучше использовать другие структуры данных, такие как связанный список, а иногда - нет.
Одним из хороших свойств массива является то, что он имеет постоянный поиск по времени, если вы знаете индекс. Постоянный поиск по времени означает, что независимо от того, сколько данных у вас в массиве, получение данных из массива займет примерно одинаковое количество времени, если вы знаете индекс. Давайте посмотрим на несколько примеров.
Я создал 1k массивов с размерами от 1 до 1k, затем я выбрал случайный индекс, который находится в диапазоне, и вычислил, сколько раз потребовалось для поиска элемента в массиве. Вы можете видеть, что время поиска на самом деле не меняется с увеличением количества элементов в массиве. Это означает, что почти нет корреляции между временем, затрачиваемым на поиск, и количеством элементов в массиве.
Но у массивов есть и минусы. Массивы имеют линейное время, когда вы вставляете в них элемент, в то время как другие структуры данных, такие как связанные списки, имеют постоянное время. Я не буду вдаваться в подробности, поскольку обе структуры данных будут объяснены в одной из следующих статей этой серии блогов. Вывод заключается в том, что вы можете писать более эффективный код, если хорошо разбираетесь в структурах данных и алгоритмах.
Что такое алгоритмы?
Короче говоря, алгоритмы - это способы решения проблем с использованием различных типов структур данных. Алгоритмы могут быть очень сложными для понимания, но давайте рассмотрим простой пример, чтобы понять, как выглядит алгоритм. Ниже приведен пример вопроса, заданного на LeetCode.
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Проблема, которую вам здесь нужно решить, довольно очевидна. По сути, вам нужно найти пару чисел, которые в сумме дают целевое значение и возвращают индексы обоих двух чисел. Простой алгоритм, который вы можете придумать, состоит в том, чтобы иметь один цикл, который перебирает числа одно за другим, и другой цикл для проверки того, совпадает ли пара чисел с целевым значением или нет. Давайте посмотрим на наивный подход к решению этой проблемы с помощью кода.
Этот код, очевидно, работает, но в нем есть два цикла - один для проверки каждого числа, а другой для проверки того, соответствует ли какое-либо число в массиве целевому значению. Фактически, вы можете удалить внутренний цикл, чтобы очистить код, если вы знаете другие структуры данных, такие как использование хэш-карт вместо использования массивов. Давайте напишем алгоритм без внутреннего цикла, вместо этого будем использовать хеш-карты.
Фактически оба этих алгоритма решают именно эту проблему. Оба они дают одинаковый результат. Здесь важно то, что если вы хорошо разбираетесь в структурах данных и алгоритмах, вы можете писать очень эффективный код. Но как узнать, насколько быстрее работает ваш эффективный алгоритм? Вот где в игру вступает нотация Big-O!
Что такое нотация Big-O?
Я представил два алгоритма для решения простой задачи. Оба они решают проблему, но один из них работает намного быстрее, чем другой, и я хочу показать вам, как доказать, что это так.
Я запустил обе функции сверху с одними и теми же входными данными и целью. В результате оптимальный подход работает немного быстрее, чем другая функция, но разница между ними действительно незначительна. Теперь давайте увеличим размер массива и посмотрим, что произойдет.
Вы можете ясно видеть, что разница между двумя функциями более значительна, чем раньше. Вы можете догадаться, почему? Ответ на этот вопрос заключается в том, что время выполнения наивного подхода растет экспоненциально по мере увеличения размера массива. Обозначение Big-O отлично подходит для выражения отношения времени выполнения и размера массива.
Обозначение Big-O указывает на эффективность вашего алгоритма с учетом входных данных. Представим, что размер входного массива равен N. Как вы думаете, сколько раз цикл выполняется при наивном подходе? Внешний цикл проходит от 0 до N, а внутренний цикл проходит от i + 1 до N. Это очень распространенное поведение для алгоритмов, и общее количество запусков цикла составляет N (N-1) / 2 раза. Это в точности то же самое, что сказать: «Если размер входа равен N, то время выполнения функции будет N (N-1) / 2», и это очень близко к определению Big-O. обозначение с еще одной модификацией - которую вы наверняка хотели бы;)
Фактически, нотация Big-O не заботится о точном времени выполнения, а о приблизительном времени выполнения. Если вы произведете некоторые вычисления для среды выполнения, которую я определил выше, она станет N²-N / 2. Big-O заботится только о самом значимом члене уравнения и игнорирует все остальное. Таким образом, время выполнения для наивного подхода и оптимального подхода становится O (N²) и O (N) соответственно. Есть и другие метрики, которые можно использовать для объяснения сложности ваших алгоритмов, например Big-Ω или Big-Θ. Но Big-O - наиболее часто используемый среди них, поэтому я не буду объяснять, чем Big-Ω или Big-отличаются от Big-O. Вывод из этого раздела заключается в том, что с помощью нотации Big-O вы можете объяснить эффективность своего алгоритма.
Заключение
В этом сообщении блога я поделился дополнительной информацией о структурах данных и алгоритмах. Всегда лучше писать эффективные программы с точки зрения времени выполнения и места на вашем компьютере. Возможно, вы не используете эти алгоритмы в своей работе, но иногда это действительно помогает писать эффективное программное обеспечение, так что это определенно стоит потраченного времени. Возможно, вы изучаете структуры данных и алгоритмы для предстоящего собеседования или для занятий в колледже. В любом случае, я надеюсь, что это сообщение в блоге помогло вам понять основы темы.
В следующем сообщении в блоге этой серии я расскажу о некоторых структурах данных, которые широко используются для разработки программного обеспечения. Большое спасибо за прочтение этого сообщения в блоге. Я сделаю все возможное, чтобы написать следующий пост как можно скорее, но пока не забудьте оставить 50 аплодисментов, чтобы мотивировать мой следующий пост;)
