Сообщения

Основные структуры данных: Хэш-таблицы

Изображение
Введение в хеш-таблицы Хеш-таблица представляет собой обобщение обычного массива. Однако в то время как ключом массива может быть только число, для хеш-таблицы им может быть любой объект, для которого можно вычислить хеш-код. Но об этом позже. Итак, интерфейс хеш-таблицы предоставляет нам следующие операции: Добавление новой пары ключ-значение Поиск значения по ключу Удаление пары ключ-значение по ключу Среднее время поиска значения по ключу в хеш-таблице равно O(1). Это значит, что в среднем, наш поиск не будет зависеть от количества элементов в хеш-таблице, и будет равен некоторому константному значению. В зависимости от самой внутренней реализации хеш-таблицы, время поиска для наихудшего случая может быть O(n), то есть линейно завесить от количества элементов в таблице, либо же оставаться O(1). Что же такое хеширование? Идея хеширования основана на распределении ключей в обычном массиве H[0..m-1]. Распределение осуществляется вычислением для каждого...
Отправить комментарий
Далее...

Основные структуры данных: Ассоциативный массив

Изображение
Ассоциативный массив (Map) — это структура, которая хранит данные в парах ключ/значение, где каждый ключ уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто используют для быстрого поиска данных. Она позволяет делать следующие вещи: добавлять пары в коллекцию; удалять пары из коллекции; изменять существующей пары; искать значение, связанное с определенным ключом. Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами. В паре значение называется значением, ассоциированным с ключом . Семантика и названия вышеупомянутых операций в разных реализациях ассоциативного массива могут отличаться. Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Две другие операции ничего не возвращают (за исключением, возможно, информации о том, успешно ли была выполнена данная операция)....
Далее...

Основные структуры данных: Множества

Изображение
Множество (set) — это структура данных, представляющая собой не организованный набор уникальных элементов одного типа. Данная структура  очень тесно связано с математическим понятием теории множеств. В наиболее упрощенном понимании, множество — это набор уникальных однотипных данных, рассматриваемых как единое целое. Давайте рассмотрим пример реализации множества и основных операций выполняемых с множествами на языке C#. На рисунке ниже схематически представлены два множества A и B, а также основные операции: объединение, пересечение, разность. Set Давайте подробнее рассмотрим все наиболее часто встречающиеся операции над множествами: Add — добавление элемента. Если такой элемент уже присутствует, то он не будет добавлен. Remove — удаление элемента из множества. Union — объединение множеств. Создается новое множество, включающее в себя все элементы из множества А и множества В. Если элемент содержится в обоих множествах, он будет добавлен однократно. Difference...
Далее...

Основные структуры данных: Стеки и очереди

Изображение
Стек Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это значит, что мы будем иметь доступ только к последнему добавленному элементу. В отличие от списков, мы не можем получить доступ к произвольному элементу стека. Мы можем только добавлять или удалять элементы с помощью специальных методов. У стека нет также метода Contains, как у списков. Кроме того, у стека нет итератора. Для того, чтобы понимать, почему на стек накладываются такие ограничения, давайте посмотрим на то, как он работает и как используется. Графически его удобно изобразить в виде вертикального списка (см. рис.), например, стопки книг, где чтобы воспользоваться одной из них, и не нарушить установленный порядок, нужно поднять все те книги, что лежат выше нее, а положить книгу можно лишь поверх всех остальных. Стек, чаще всего, реализуется на основе обычных массивов, односвязных и двусвязных списков. В зависимости от конкретных ...
Далее...

Основные структуры данных: Связанные списки

Изображение
Связный список является простейшим типом данных динамической структуры, состоящей из элементов ( узлов ).  Каждый узел включает в себя в классическом варианте два поля: данные (в качестве данных может выступать переменная, объект класса или структуры и т. д.) указатель на следующий узел в списке. Доступ к списку осуществляется через указатель, который содержит адрес первого элемента списка, называемый  корнем списка .  Элементы связанного списка можно помещать и исключать произвольным образом. Классификация списков По количеству полей указателей  различают однонаправленный (односвязный) и двунаправленный (двусвязный) списки. Связный список, содержащий только один указатель на следующий элемент, называется односвязным. Связный список, содержащий два поля указателя – на следующий элемент и на предыдущий, называется двусвязным. По способу связи элементов  различают линейные и циклические списки. Связный список, в котором,...
Далее...

Сложность алгоритмов

Изображение
Асимптотический анализ Когда мы говорим об измерении сложности алгоритмов, мы подразумеваем анализ времени, которое потребуется для обработки очень большого набора данных. Такой анализ называют асимптотическим. Сколько времени потребуется на обработку массива из десяти элементов? Тысячи? Десяти миллионов? Если алгоритм обрабатывает тысячу элементов за пять миллисекунд, что случится, если мы передадим в него миллион? Будет ли он выполняться пять минут или пять лет? Порядок роста Порядок роста описывает то, как сложность алгоритма растет с увеличением размера входных данных. Чаще всего он представлен в виде O-нотации (от нем. «Ordnung» — порядок) : O(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных. Ниже приводится список наиболее часто встречающихся порядков роста, но он ни в коем случае не полный. Что мы измеряем? При измерении сложности алгоритмов и структур данных мы обы...
Далее...

Алгоритмы распределения случайных величин

Изображение
Равномерное распределение Распределение случайной вещественной величины, принимающей значения, принадлежащие интервалу [a, b], характеризующееся тем, что плотность вероятности на этом интервале постоянна.                                                              Равномерное распределение может использоваться при генерации почти что любой случайной величины. Нормальное распределение Распределение вероятностей, которое играет важнейшую роль во многих областях знаний. Случайная величина подчиняется нормальному закону распределения, когда она подвержена влиянию большого числа случайных факторов, что является типичной ситуацией в анализе данных. Поэтому нормальное распределение является хорошей моделью для многих реальных процессов. Смысл нормального распределения становится понятен из его формы. Н...
Далее...