Главная » Структуры данных и алгоритмы

Использование нотации большого О

Добавлено Дата: 7 January, 2012 категория: Java, Структуры данных и алгоритмы

Считается дурным тоном говорить, что «/(я) < 0(g (я))», так как определение нотации большого О уже содержит «меньше или равно». В то же время, несмотря на распространенное употребление, не вполне корректно записать «/(я) = 0(g(n))» (в обычном понимании отношений, обозначенных символом «=»), и совершенно не верно, что «/(я) > 0(g(n))», или «/(Л) > 0(g(n))». Оптимальным выходом будет определение «/(я) есть 0(g(n))». Либо, используя математические символы, данное отношение можно выразить следующим образом:

Читать »

AVL-деревья

Добавлено Дата: 7 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Операторы цикла Java

Добавлено Дата: 7 January, 2012 категория: Java, Структуры данных и алгоритмы

Важным механизмом алгоритма управления в языке программирования является понятие циклов. В Java встроены три типа циклов.

Цикл for

Простейшая форма оператора цикла for предусматривает повторение заданной последовательности операторов на основании целочисленного индекса. Однако Java предлагает и другие достаточно широкие возможности оператора for. В частности, сам процесс работы оператора for можно разделить на четыре части: инициализация, условие, инкремент и тело оператора. Запись оператора for осуществляется следующим образом:

Читать »

Классы, типы и объекты Java

Добавлено Дата: 7 January, 2012 категория: Java, Структуры данных и алгоритмы

 

Приступим к рассмотрению классов и объектов языка Java — центральных понятий программирования в нем. Главными элементами языка Java являются объекты. Объекты содержат данные и методы доступа и изменения этих данных. Каждый объект представляет экземпляр определенного класса, описывающий тип содержащихся в объекте данных, а также операции, которые могут выполняться над данными. Ниже приводятся некоторые из возможных членов класса в языке Java:

Читать »

Бинарное поисковое дерево Производительность

Добавлено Дата: 6 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Утверждение 9.1. Бинарное поисковое дерево Т высотой h для п объектов «ключ-элемент» требует О(п) места и выполняет операции АТД «словарь» за следующее время:

Читать »

Бинарные деревья

Добавлено Дата: 6 January, 2012 категория: Java, Структуры данных и алгоритмы

Одним из видов деревьев, представляющих особый интерес, является бинарное дерево. Как установлено в п. 6.1.1, правильным бинарным деревом является упорядоченное дерево, в котором каждый составной узел имеет два дочерних элемента. Более того, там же специально оговорено, что бинарные деревья считаются правильными, если только’обратное не будет отмечено специально. Заметим, что это условие никоим образом не нарушает целостности понятия, следовательно, любое неправильное бинарное дерево может быть легко преобразовано в правильное, в чем можно убедиться, выполнив упражнение М-6.3. И даже, отказавшись от этого условия, можно считать неправильное бинарное дерево правильным, рассматривая недостающие простые узлы как «нулевые узлы» или установив заглушки, выступающие в роли узлов.

Читать »

Сравнительный анализ различных реализаций последовательности

Добавлено Дата: 5 January, 2012 категория: Java, Структуры данных и алгоритмы

В табл. 5.4 представлены результаты сравнения времени выполнения реализации универсального АТД «последовательность» с помощью массива (цикличный вариант) и двусвязного списка.

Читать »

Структура матрицы смежности

Добавлено Дата: 5 January, 2012 категория: Java, Структуры данных и алгоритмы

Как и в случае со списком смежности, матрица смежности расширяет структуру списка путей с помощью дополнительных компонентов. В данном случае в список путей добавляется матрица (двухмерный массив) А, что позволяет определять смежности пар узлов за пропорциональный 0(1) промежуток времени. Как будет показано далее, такое повышение скорости требует значительных объемов памяти.

Читать »

Методы очереди с приоритетами

Добавлено Дата: 4 January, 2012 категория: Java, Структуры данных и алгоритмы

Описав абстрактный тип данных очереди с приоритетами на интуитивном уровне, перейдем к более детальному анализу. Как АТД, очередь с приоритетами Р поддерживает следующие методы:

size(): возвращает количество элементов в очереди Р. Input: отсутствует; Output: целое число.

Читать »

Внутренняя быстрая сортировка

Добавлено Дата: 3 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Сортировка методом слияния и рекуррентные соотношения

Добавлено Дата: 3 January, 2012 категория: Java, Структуры данных и алгоритмы

Существует еще один способ обоснования утверждения 10.3, гласящего, что время выполнения алгоритма сортировки равно О(п log п), в основу которого положена рекурсивная природа алгоритма сортировки методом слияния. В этом разделе содержится именно такой анализ алгоритма сортировки, и по этой причине представляется математическая концепция рекуррентных отношений (recurrence relation).

Читать »

Алгоритмы шаблонного сопоставления Алгоритм Бойера-Мура

Добавлено Дата: 3 January, 2012 категория: Java, Структуры данных и алгоритмы

Поначалу может показаться, что в любом случае придется проходить каждый символ из Г в поисках подстроки, соответствующей шаблону Р. Но только не в случае с алгоритмом Бойера-Мура (Воуег-Мооге), или БМ-алгоритмом, который иногда позволяет избежать сравнения между шаблоном Р и сравнительно большой частью символов Т. Следует только предупредить, что силовой алгоритм может работать даже с потенциально неограниченными словарями, в то время как БМ-алгоритм исходит из установленного конечного размера алфавита. Он работает быстрее, если алфавит имеет разумный размер, а шаблон достаточно велик. БМ-алгоритм идеально подходит для поиска слов в текстовом документе. В этом разделе опишем упрощенный вариант оригинального алгоритма Бойера-Мура.

Читать »

Класс String в Java

Добавлено Дата: 3 January, 2012 категория: Java, Структуры данных и алгоритмы

Основные операции класса String перечислены ню?е:

length(): возвращает длину п строки S. Input: отсутствует; Output: int.

charAt(/): возвращает символ, имеющий индекс / из строки S. Input: int; Output: char.

startsWith(0: определяет, является ли Q префиксом строки S. Input: String; Output: boolean. *

Читать »

Регистрационные файлы (log-файлы)

Добавлено Дата: 2 January, 2012 категория: Java, Структуры данных и алгоритмы

Простейшим способом реализации словаря является неупорядоченный вектор, список или обычная последовательность для хранения пар «ключ-элемент». Такая реализация обычно называется регистрационным файлом (log file), или контрольным следом (audit trail). Основной сферой применения таких видов реализации являются ситуации, где требуется архивация структурированных данных. Например, многие финансовые базы данных хранят таким способом словари всех своих транзакций. Точно так же многие программные операционные системы, такие как Web-серверы и программы удаленной регистрации, хранят регистрационные файлы всех обработанных через Интернет запросов. Типичным сценарием этих приложений является большое количество вводимых данных и небольшое количество поисковых запросов. Например, поиск в регистрационном файле таких систем обычно осуществляется только в случаях необходимости анализа нестандартных ситуаций, вроде сбоя в системе. Таким образом, регистрационные файлы должны поддерживать простой и быстрый ввод данных, возможно, в ущерб времени на поиск. Формально можно сказать, что регистрационный файл представляет собой реализацию словаря Д использующего последовательность S (для полной универсальности), чтобы хранить объекты из D в произвольном порядке (см. рис. 8.2).

Читать »

Стеки в виртуальной машине Java

Добавлено Дата: 2 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Java является ключевым в. определении самого < языка Java j Благодаря тому, что’при компиляции Java-код преобразуется в байтгкоды виртуальной машины Java, а не в команды какого-либо конкретногр процессора, Java-nporpaMMa может далее выполняться на любом компьютере, включая рабочии станции UNIX, способном к эмуляции виртуальной машины Java. Следует отметить;, что стековая структура данных является основой определения виртуальной машины Java.

Читать »