RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2012, том 92, выпуск 4, страницы 528–532 (Mi mzm9091)

Сравнение скорости сходимости чисто жадного и ортогонального жадного алгоритмов

А. В. Деревенцов

Московский государственный университет им. М. В. Ломоносова

Аннотация: В работе рассматриваются два вида жадных алгоритмов: чисто жадный алгоритм (PGA) и ортогональный жадный алгоритм (OGA). С точки зрения оценок скорости сходимости на всем классе $\mathscr A_1(\mathscr D)$ ортогональный жадный алгоритм оптимален и существенно превосходит чисто жадный алгоритм. Основным результатом настоящей работы является утверждение, показывающее, что для отдельных элементов класса $\mathscr A_1(\mathscr D)$ (и даже $\mathscr A_0(\mathscr D)$) ситуация может быть и противоположной: скорость сходимости ортогонального жадного алгоритма может быть существенно ниже скорости сходимости чисто жадного алгоритма.
Библиография: 16 названий.

УДК: 517.518+519.65

Поступило: 01.12.2010
Исправленный вариант: 22.03.2011

DOI: 10.4213/mzm9091


 Англоязычная версия: Mathematical Notes, 2012, 92:4, 485–489

Реферативные базы данных:


© МИАН, 2024