Я искал хороший онлайн-курс по структурам данных, но обнаружил, что Google также возвращает результаты для курсов по алгоритмам, которые говорят что-то вроде:

В этом курсе вы изучите несколько фундаментальных принципов построения алгоритмов: методы «разделяй и властвуй», алгоритмы графов, практические структуры данных (кучи, хеш-таблицы, деревья поиска) , рандомизированные алгоритмы и многое другое. [источник]

и

К концу этого занятия вы поймете ключевые понятия, необходимые для разработки новых алгоритмов для графов и других важных структур данных и для оценки эффективности этих алгоритмов. [источник]

и

Этот курс представляет собой введение в математическое моделирование вычислительных задач. Он охватывает общие алгоритмы, алгоритмические парадигмы и структуры данных, используемые для решения этих проблем . [источник]

Мой вопрос: тесно ли связаны алгоритмы и структуры данных, что означает, что они должны пониматься вместе, или одна тема является более фундаментальной, чем другая?

РЕДАКТИРОВАТЬ: Для тех, кто голосует, чтобы закрыть этот вопрос, не могли бы вы сказать мне, почему и, возможно, как улучшить этот вопрос? Умение задавать правильные вопросы является частью образовательного процесса.

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

Редактировать: как правильно указал @Doval, структуры данных сами по себе не имеют никаких операций, связанных с ними. Акт объединения структуры данных и алгоритма формирует абстрактный тип данных.

Структуры данных без алгоритмов

Рассмотрим, например, структуру данных для хранения двумерных координат, которая называется соответствующим образом Point. Нет ничего особенного с точки зрения алгоритмов, которые нужно сделать для точки, и это на самом деле просто контейнер для xи yзначения. Конечно, предоставив эту структуру данных, вы можете добавить к ней все виды алгоритмов (расчет расстояния, выпуклые оболочки, что у вас).

Вы можете думать о множестве структур данных, которые представляют собой просто набор отдельных данных. Хотя это часто происходит на практике, они не являются хорошим учебным материалом, потому что из этого нечего извлекать уроки, как только вы поняли, что отдельные элементы данных могут быть собраны в новую структуру данных (например, то, что вы изучаете) после приведенного выше Pointпримера, если я предоставлю вам эту удивительную структуру данных Point3D, которая может сделать то же самое для трехмерного пространства?)

Алгоритмы без (реальных) структур данных

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

Примером такого алгоритма будет вычисление наибольшего общего делителя двух чисел. Алгоритмы Евклида для gcd действительно должны содержать только два целых числа и манипулировать ими.

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

Алгоритмы в сочетании со структурами данных, или абстрактные типы данных

Теперь это интересные, но по двум очень разным причинам. Как правило, вы можете подойти к ним с двух сторон: сначала структура данных или сначала алгоритм.

Хотя абстрактный тип данных определяется комбинацией структуры данных + алгоритмы / операции, мы часто рассматриваем их с акцентом на одном из них и рассматриваем другой как вспомогательные.

Структура данных, затем алгоритм

Вы столкнетесь с абстрактными типами данных, которые довольно просты в использовании, но используют более или менее сложные алгоритмы для обеспечения их внутренней работы. Например, a HashMapтривиально для использования, но включает в себя изящную хеш-функцию и имеет дело с коллизиями хеша внутри. Тем не менее, с вашей точки зрения, как пользователя, вы заботитесь о нем как о чем-то, что хранит данные для вас, а не как о чем-то, что делает что-то для вас.

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

Алгоритм, то структура данных

Другое направление означает, что у вас есть алгоритм, который вы хотите просто использовать, но который требует внутренних структур данных, чтобы он работал как задумано. Примером может служить алгоритм разделения двоичного пространства (BSP), который можно просто запросить для двумерного Pointиз большого набора точек, ближайшего к данной точке запроса. Тем не менее, вам нужна древовидная структура (и даже дополнительные алгоритмы, такие как вычисления расстояний) внутри, чтобы фактически написать алгоритм.

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

Тесно связанные структуры данных и алгоритмы

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

В этих случаях мы часто меняем фокус нашего представления о результирующих абстрактных типах данных. Иногда вы заботитесь о структуре вашего дерева, через несколько минут вы заботитесь о возможности запустить на нем операцию поиска, затем вам интересно удалить узел и сразу же узнать, как структура будет выглядеть потом. Хотя все это верно и для других разделов выше, это не то, что является основным направлением вашего внимания, например, когда вы сохраняете / извлекаете данные в / из Map, или когда вы сортируете связанный список.

Структуры данных часто влияют на детали алгоритма. Из-за этого они часто идут рука об руку.

Рассмотрим, например, алгоритм стрижки вашего газона. То, как вы будете подстригать газон, вероятно, будет зависеть от фактической структуры вашего газона. Если вы живете в небольшом доме в густонаселенном пригороде и ваш газон представляет собой небольшой прямоугольник площадью в несколько метров, вы, вероятно, предпочли бы подстригать газон с помощью косилки-толкача, а не тракторной / ездовой косилки. Если ваш газон занимает много акров равнинной луговой земли, вы можете предпочесть верховую газонокосилку, а не газонокосилку (хотя любая газонокосилка может в конечном итоге выполнить работу). Если ваш газон включает в себя акры земли с большими ровными участками, но с несколькими небольшими холмами и множеством деревьев, вы можете разработать более интересный алгоритм для стрижки газона, который включает в себя как газонокосилку-качалку, так и толкающую косилку, или какую-то другую траву. Техника резки.

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

И наоборот: иногда алгоритм, который мы хотим использовать, влияет (по крайней мере, в начале вычислений) на структуры данных, которые вы разрабатываете для поддержки алгоритма. Например, переход от списка массивов к идее связанного списка и в конечном итоге к BST для хранения упорядоченного списка, который позволит быстро найти.