Главная » Java, Структуры данных и алгоритмы » Сведения из области математики

0

Настоящее приложение содержит некоторые математические сведения, свойства и правила.

Логарифмическая и показательная функции

Логарифмическая функция определяется как

Полезные математические правила

Для определенного типа функций можно воспользоваться соответствующими правилами.

Утверждение А. 19. Правило Лопиталя. Если lim /(п) = +оо и lim g(n) = +оо,

Л->оо                                                                         п-> оо

тогде f\n) и g'(n) соответственно производные f(n)

и g(n).

При вычислении верхней и нижней границ суммы следует разбивать операцию суммирования следующим образом:

Еще одним полезным правилом является интегральное ограничение суммы. Если / неубывающая функция, то при выполнении следующего условия:

существует универсальная форма рекуррентных отношений, возникающих при анализе алгоритмов «разделяй и властвуй»:

для постоянных а > 1 и b > 1.

Утверждение А.20. Пусть Т(п) будет определено таким образом, как это указано выше. Тогда:

1.  Еслидля некоторой постоянной е > 0, то Т(п) составляет

2.  Если/(л) естьдля некоторого неотрицательного целого числа к > 0, то Т\п) составляет

3.  Если f(n) естьдля некоторой постоянной е > 0, а af(n/b) < cf(n), то Т(п) составляет 0(/(л)).

Это утверждение получило название главного метода (master method) для асимптотической характеристики рекуррентных отношений типа «разделяй и властвуй».

2 Зак. 2456

•     используйте в качестве идентификаторов значащие имена, которые можно произнести, или’имена, отражающие действие, функции или данные именуемого объекта. В Java принято записывать каждое слово идентификатора с прописной буквы, за исключением методов и переменных, в именах которых первое слово начинается строчной буквой. Например, согласно указанной -Традиции идентификаторы «Date», «Vector», «DeviceManager» являются именами классов, a>«isFull()», «insertltem()» «studentName» и «studentHeight» — соотт ветственно идентификаторы методов и переменных;

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

•                , Амортизация (п. 5.1.3)

•                                   «Разделяй и властвуй» (п. 10.1.1)

•                                   «Отсекай и ищи», или «Сокращай и властвуй» (п. 10.7.1)

•                                   «Грубая сила» (п. 11.2.1)

•                                   Каскадный метод (п. 11.4.2)

•                                   Динамическое программирование (п. 11.5.2)

• Выражения. Для написания числовых и логических выражений ис

5 Зак 2456

*        добавляет элемент в стек.

*        param element добавляемый элемент.

7

^ public void push (Object element); Г*

*        удаляет последний элемент стека.

*         возвращает удаленный элемент.

*         исключение StackEmptyException, если стек пуст. 7

public Object рор()

throws StackEmptyException;

}

Фрагмент кода 4.1. Интерфейс Stack с комментариями Javadoc (см. п. 1.9.2)

О возникновении ошибки при обращении методов рор() и top() к пустому стеку свидетельствует сообщение об исключении типа StackEmptyException, описанное во фрагменте кода 4.2.

•     введем новый АТД под названием inspectable vector (инспектирующий вектор), который содержит только методы запросов size и isEmpty, а также метод доступа elemAtRank;

•          переопределим вектор как АТД, который расширяет инспектирующий вектор и добавляет методы обновления replaceAtRank, insert- Rank и removeAtRank.

1) количество простых узлов дерева Гравно минимум h + 1 и максимум 2Л;

•          если левый дочерний элемент г составной, а правый — простой, то пусть s будет левым дочерним элементом г;

•                    если же нет (оба дочерних элемента г — составные узлы), пусть s будет дочерним элементом г с наименьшим ключом.

•          высота пирамиды Гесть 0(log п), так как Гявляется завершенной;

•                   в крайнем случае восходящая и нисходящая сортировки занимают время, пропорциональное высоте Т\

1. Воспользуемся обратно направленным компаратором, соответст

• findElement(A:): возвращает элемент объекта с ключом к, если таковой существует;

•     если один из дочерних элементов w является простым узлом, например г, то удаляем w и г из Тс помощью операции removeAboveExternal(z). Эта операция (см. рис. 6.13 и п. 6.4.2) реструктурирует Г, замещая w соседним узлом z и удаляя w и z из Т. Такой случай показан на рис. 9.5;

•          если оба дочерних элемента w являются составными узлами, то просто удалить узел w из Г нельзя, так как появится «дыра» в Т. Вместо этого производится следующее;

3)                     компактного trie для множества индексных термов, в котором каждый простой узел хранит индекс списка появлений ассоциируемого с ним ключевого слова.

 

 

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии