Комментарии 7
Спасибо, интересная статья!
Я правильно понимаю, что оценка применима только для линейных нормированных пространств входных данных? То есть, скажем, для алгоритма Дейкстры нельзя посчитать smoothed оценку, хотя на множестве графов и можно ввести корректную метрику.
И перепроверьте, пожалуйста, формулу — в ней точно x и r не перепутаны местами? А то получается, что r — это элемент входных данных, и он умножается на коэффициент sigma, на норму x, потом складывается с x и получается новый элемент входных данных.
И, кстати, к какому множеству принадлежит r? Если это единичный шар в пространстве входных данных (что было бы логично предположить для большинства применимых на практике случаев), то формулу можно переписать в 100 раз понятнее через понятие эпсилон-окрестности. Заодно, кстати, и требование линейности пространства входных данных пропадет, останется лишь метричность.
Я правильно понимаю, что оценка применима только для линейных нормированных пространств входных данных? То есть, скажем, для алгоритма Дейкстры нельзя посчитать smoothed оценку, хотя на множестве графов и можно ввести корректную метрику.
И перепроверьте, пожалуйста, формулу — в ней точно x и r не перепутаны местами? А то получается, что r — это элемент входных данных, и он умножается на коэффициент sigma, на норму x, потом складывается с x и получается новый элемент входных данных.
И, кстати, к какому множеству принадлежит r? Если это единичный шар в пространстве входных данных (что было бы логично предположить для большинства применимых на практике случаев), то формулу можно переписать в 100 раз понятнее через понятие эпсилон-окрестности. Заодно, кстати, и требование линейности пространства входных данных пропадет, останется лишь метричность.
Тут действительно есть некоторое лукавство т.к. для большинства задач ввести близость решений можно по разному, что будет менять smoothed оценку. Например можно взять все возможные входы, отсортировать по времени их обработки и тогда всегда smoothed оценка будет близка к максимуму. Насколько я понимаю (но это не точно) здесь делается неявно такое предположение, что выбранная функция расстояния не будет скоррелирована с временем работы. И если у алгоритма smoothed оценка близка к худшей, значит подобрать группу плохих задач для него достаточно легко. И наоборот если она ближе к среднему, то подобрать такую группу сложно. Думаю можно даже доказать теорему, что выбранные случайным образом две функции расстояния дают в среднем не слишком разные оценки. Но формула действительно написана так, что должна существовать операция сложения на входных данных и умножения на коэффициент, кажется из этого следует линейность.
x — это центр шара в котором мы считаем среднее, r действительно некоторый случайный вектор по которому мы берем среднее (он чисто по размерности должен быть из пространства поиска). По идее его длина не очень важна т.к. у нас есть сигма для нормировки. К слову в статье вектор берут по всему пространству поиска, но распределен он нормально от длины.
x — это центр шара в котором мы считаем среднее, r действительно некоторый случайный вектор по которому мы берем среднее (он чисто по размерности должен быть из пространства поиска). По идее его длина не очень важна т.к. у нас есть сигма для нормировки. К слову в статье вектор берут по всему пространству поиска, но распределен он нормально от длины.
Несмотря на то, что чтение из L1 кэша примерно в 200 раз медленнее
быстрее
Тут нарисовано распределение времени по множеству входных данных для некоторого n.
Пардон, я не понял: что значит "нарисовано распределение", почему области двумерные?
Области не двумерные. Тут нарисовано просто абстрактное множество всех возможных входов длины n (из формул так же вытекает, что оно нормированное, но никаких предположений о его размерности не делается). А оценки времени работы на конкретном входе выделены на множестве цветом. Это не распределение вероятности, тут слово «распределение» употреблено в обычном своем значении, а не в вероятностном.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Дополнение к анализу алгоритмов