Big-O и Cache Aware Data Структуры и алгоритмы данных

Question

Есть ли место, где я могу получить анализ в стиле Big-O / сравнение традиционных структур данных, таких как связанные списки, различные деревья, хэши и т. Д., Со структурами данных с поддержкой кэширования, такими как деревья Джуди и другие?

Answer 1

На самом деле,

Я бы посмотрел здесь для анализа Джуди Трэс.

Как показано в этих данных, Джуди меньший размер не дает ему огромное преимущество в скорости перед традиционный «размер сделки для скорости» структура данных. Джуди получила бесчисленные человеко-часы развиваются и отладка 20 000 строк кода; я потратил час или три на написание довольно стандартный 200-строчный хэш-стол.

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

Answer 2

BigO - это сложность алгоритмов, выполняющих определенную задачу. Для каждой структуры данных доступны разные задачи. Наиболее важные из них: Сортировка, поиск (в отсортированной структуре) и добавление элемента.

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

Для большинства типов данных оптимальным алгоритмом сортировки является O (n log (n)), но имейте в виду, что некоторые структуры все еще работают медленнее, например, сортировка связанного списка медленнее, чем у массивов, хотя оба имеют лог * n (n) сложность

Answer 3

Вы смотрели в: "Введение в алгоритмы"

(http://en.wikipedia.org/wiki/Introduction_to_Algorithms)

Answer 4

Читать Искусство компьютерного программирования книги Дона Кнута. Многие считают, что это лучший источник информации об алгоритмах.