powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Верификация сложности алгоритма
118 сообщений из 118, показаны все 5 страниц
Верификация сложности алгоритма
    #39827176
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Предположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить, верно ли предположение о сложности?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827179
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
плавно увеличивать N и замерять время работы алгоритма в различных попугаях ?

100-120-144-172-207...-1000000000000
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827207
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklinплавно увеличивать N и замерять время работы алгоритма в различных попугаях ?

100-120-144-172-207...-1000000000000

И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827208
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827209
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
График, построенные по результатам эксперимента, должен совпасть с графиком, построенным на теоретических данных, с заданной точностью.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827211
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinInterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности.

Насколько большое N нужно брать для графика?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827214
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperНасколько большое N нужно брать для графика?Зависит от того, под какие данные рассчитан алгоритм.

Если речь идет про простую сферическую в вакууме сортировку уровня студенческих лабораторных, то я бы сказал, что достаточно взять до миллиона элементов.

Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827215
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinInterloperНасколько большое N нужно брать для графика?Зависит от того, под какие данные рассчитан алгоритм.

Если речь идет про простую сферическую в вакууме сортировку уровня студенческих лабораторных, то я бы сказал, что достаточно взять до миллиона элементов.

Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство.

В том то и дело, что мы не знаем как устроен алгоритм внутри.
Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827219
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?

Делить время на сложность - должно асимптотически приближать к некоторой константе, т.е. Время/(n*log(n)), для Вашего примера.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827220
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperВ том то и дело, что мы не знаем как устроен алгоритм внутри.
Если у алгоритма нет генератора случайных чисел в виде одного из параметров "работы", то пройдитесь от 1 до 2^K, каждый раз увеличивая размер чисел вдвое. Делая несколько замеров на каждом N, с разными входными данными. Верхний предел - простое любопытство, время, при котором компьютер будет гонять алгоритм достаточно продолжительное для вашего ожидания время. В некоторых случаях это могут и быть и сутки, но для простых замеров достаточно, чтобы алгоритм работал одну-две минуты.

Если есть генератор случайных чисел и он определяет сложность, и погрешность при этом велика, то никак вы не определите, что там внутри. Для одних и тех же данных время может различаться, либо различаться не на одних и тех же, а скажем на соседних данных (с точки зрения алгоритма). Например, 2+2 будет складываться одну минуту, а 2+3 уже пятнадцать минут.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827232
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827233
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064InterloperИ как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?

Делить время на сложность - должно асимптотически приближать к некоторой константе, т.е. Время/(n*log(n)), для Вашего примера.

Каков алгоритм проверки на асимптотическое приближение?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827255
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperAklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827256
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Interloper
Каков алгоритм проверки на асимптотическое приближение?

Я бы попробовал метод наименьших квадратов для линейного приближения: если угол наклона стремится к 0, значит приближаемся к асимптоте.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827261
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneInterloperAklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.

Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827262
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064InterloperКаков алгоритм проверки на асимптотическое приближение?

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

Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827267
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Interloper
Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?

У Вас есть набор точек Y=(Время)/(Сложность) от X=(Сложность), после МНК получим:
Y=a*X+b, если a мало (внешний задаваемый параметр, означет точность нашего диагноза), значит (Время)=O(Сложность)
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827269
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperBarloneпропущено...
Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.

Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.А вам с какой целью? Успешная проверка на некотором наборе вариантов не будет являться доказательством вашего предположения. Если конечно это не полный перебор всех возможных вариантов входных данных.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827271
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneInterloperпропущено...


Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.А вам с какой целью? Успешная проверка на некотором наборе вариантов не будет являться доказательством вашего предположения. Если конечно это не полный перебор всех возможных вариантов входных данных.

Мне чисто из интереса.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827276
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064InterloperНаклона чего по отношению к чему? Как будем оценивать стремление к нулю?

У Вас есть набор точек Y=(Время)/(Сложность) от X=(Сложность), после МНК получим:
Y=a*X+b, если a мало (внешний задаваемый параметр, означет точность нашего диагноза), значит (Время)=O(Сложность)

МНК даст нам оценку отклонения нашей функции от некоторой эталонной. Какую считать эталонной для O(N*N)? Нам то неизвестны коэффициенты, "спрятанные" внутри О большое.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827278
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если чисто из интереса, то непонятна претензия:
InterloperДля N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.
В любом случае, у программной реализации есть ограничения на входные данные: какое количество данных помещается в память, помещаются ли сами значения в используемый тип...
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827286
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если алгоритм работает с каким-то массивом, то константа про О большом будет меняться в момент, когда массив перестанет помещаться в кеш.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827287
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneЕсли чисто из интереса, то непонятна претензия:
InterloperДля N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.
В любом случае, у программной реализации есть ограничения на входные данные: какое количество данных помещается в память, помещаются ли сами значения в используемый тип...
Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827291
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperЧисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827300
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneInterloperЧисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.

То есть такой проверяющий алгоритм не существует?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827444
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperBarloneпропущено...
Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.

То есть такой проверяющий алгоритм не существует?
Твои уточняющие вопросы напоминают легкий троллинг отвечающих.
Тебе уже в первом ответе дали методику.

Ты ее применил? Ты нарисовал график в Excel?

Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827474
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonInterloperпропущено...


То есть такой проверяющий алгоритм не существует?
Твои уточняющие вопросы напоминают легкий троллинг отвечающих.
Тебе уже в первом ответе дали методику.

Ты ее применил? Ты нарисовал график в Excel?

Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова.

График меня не интересует. Я уже понял, что проблема алгоритмически неразрешима.
Вопрос я задал фундаментальный, решение тупо взять нарисовать график, очевидно, не решает поставленную задачу.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827476
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А чего ты ожидал?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827515
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

доказательство несуществования такого проверяющего алгоритма
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827604
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Действительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм сложность O(nlogn). Покажем, как с его помощью можно решить проблему останова .

Для этого создадим алгоритм P(n, A), который будет запускать на машине Тьюринга произвольный алгоритм A на n^2 шагов. При этом, если алгоритм A остановился менее, чем за n^2 шагов, алгоритм P возвращает число шагов, за которые он остановился; если же не остановился, возвращает n^2.

Заметим, что если A останавливается за конечное число шагов m, то начиная с некоторого n=n0 алгоритм P(n, A) так же выполняется за конечное число шагов (ему не приходится проверять алгоритм A на n^2 шагов, достаточно проверить m шагов), таким образом его сложность будет O(1) <= O(nlogn). Если же алгоритм A не останавливается, алгоритм P(n, A) для каждого n будет проверять n^2 шагов алгоритма A, и его сложность будет O(n^2) > O(nlogn).

Таким образом, умея с помощью алгоритма S распознавать сложность алгоритма P(n, A) мы можем решить алгоритмически неразрешимую проблему останова. Полученное противоречие доказывает невозможность существования проверяющего алгоритма S.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827618
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperAklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.
Это несложно проверить, сделав, скажем, сто тестов на одной длине массива.


Interloperили показать, что его не существует.Скорее нужно придумать наличие факторов, которые не дадут честно замерить время. Например тот же рандом при задержках. Если задержка будет каждый раз разная и на одном и том же массиве время будет различаться, скажем, в зависимости от предыдущих данных, тогда можно смело закрывать лавочку по данному алгоритму.


Дерзайте, экспериментируйте. За вас писать весь процесс никто не станет здесь.

InterloperКаков алгоритм проверки на асимптотическое приближение?
Определение асимптоты можно в википедии прочитать, это несложно.

InterloperВнесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.Ну так определяйте величину конечности этого времени при длине массива (или числе тестов) стремящихся к бесконечности.


InterloperТо есть такой проверяющий алгоритм не существует?Существует.
Называется программист.
В зависимости от конкретного поведения конкретного алгоритма придумываются конкретные действия по его тестированию.

Но, повторюсь, если в алгоритме рандом в качестве одного из ведущих факторов, то такой алгоритм вы за конечное время выявить не сможете, а его результаты будут битые (неверные).
Поэтому встает вопрос о алгоритмической неразрешимости.
А в этом случае нужно думать уже не методами программирования, а математическими теориями.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827620
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperДействительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм сложность O(nlogn). Покажем, как с его помощью можно решить проблему останова .Не подходит. По условиям, алгоритм завершится за конечное время для любых входных данных.



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

После этого сказать что для данного алгоритма определена следующая сложность (это тоже несложно сделать) с погрешностью 2*P.

Задача решена.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827622
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperЗаметим, что если A останавливается за конечное число шагов m, то начиная с некоторого n=n0 алгоритм P(n, A) так же выполняется за конечное число шагов (ему не приходится проверять алгоритм A на n^2 шагов, достаточно проверить m шагов), таким образом его сложность будет O(1) <= O(nlogn).Неверно.

Неверный вывод из несвязанных предпосылок.
Если алгоритм имеет конечное время исполнения, это еще не значит, что у него сложность известная.
И уж тем более не значит, что она <= O(n*log(n))
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827640
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinНе подходит. По условиям, алгоритм завершится за конечное время для любых входных данных.
Это не мешает подать на вход любой алгоритм.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827642
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinНеверно.

Неверный вывод из несвязанных предпосылок.
Если алгоритм имеет конечное время исполнения, это еще не значит, что у него сложность известная.
И уж тем более не значит, что она <= O(n*log(n))

Верно. Если алгоритм при увеличении n, начиная с определенного n выполняется за конечное константное время, то его сложность O(1) <= O(nlogn).
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827646
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinПоэтому по сути решение задачи следующее: определить насколько сильной является поведение рандомной части (включая часть про зависимость от предыдущих данных) (пусть будет в процентах от общего времени исполнения это будет P). Это несложно сделать.

После этого сказать что для данного алгоритма определена следующая сложность (это тоже несложно сделать) с погрешностью 2*P.

Задача решена.

Алгоритмы детерминированы, в них нет "рандомной части". Рассматриваются алгоритмы, выполняемые на детерминированной машине Тьюринга.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827651
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperДействительно, пусть существует проверяющий алгоритм S, который может определить имеет ли произвольный алгоритм ...Дружище, вы безусловно в чём-то разбираетесь ... и немного путаетесь ...
Если вы знаете, что ваша задача из разряда неразрешимой массовой проблемы , то это не значит, что частный вариант проблемы обязательно неразрешим.
Выше уже ответили для случаев конкретных задач. Теоретизировать ступайте в теорию алгоритмов . Более того, если ваш сферический алгоритм похож на алгоритм с оракулом , то возможны всякие чудеса. Например он может в случайное время (закладка такая была) нажимать на тормоз/акселератор ... Или вообще, по команде извне ...
Кроме тестов, для чёрных ящиков не придумали лучшего.
Выбираете гипотезу, набираете статистику, проверяете гипотезу и т.д... Повезло - вы в коричневом в шоколаде ...
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827653
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98,

В чем путаюсь? Я знаю, что есть решение для частных случаев. Но меня интересует общий случай. И для общего случая проблема неразрешима.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827670
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperВерно. Если алгоритм при увеличении n, начиная с определенного n выполняется за конечное константное время, то его сложность O(1) <= O(nlogn).
ММм... может и так, но к нашей задачи это отношения все равно не имеет.


InterloperНе подходит. По условиям, алгоритм завершится за конечное время для любых входных данных.
Это не мешает подать на вход любой алгоритм.Достаточно ввести правило отлаженности (работоспособности) алгоритма и сделать вид, что любое время, выбивающееся из "разумных пределов" есть неработоспособность этого алгоритма.
Найти среднее время в пределах погрешности несложно. Если какие-то многочисленные запуски будут выбиваться из пределов погрешности, то следует говорить, что алгоритм неработоспособен (ошибочен).

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




InterloperАлгоритмы детерминированы, в них нет "рандомной части". Рассматриваются алгоритмы, выполняемые на детерминированной машине Тьюринга.Нет гарантий конечности времени исполнения на машине Тьюринга (см. выше).


InterloperНо меня интересует общий случай. И для общего случая проблема неразрешима.Общий случай на практике не встречается, только частные и конечные.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827672
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Алгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу о конечности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
3) задача решена.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827673
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу об определении сложности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
3) задача решена.

поправка*
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827675
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу об определении сложности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
2.1) Если итоговая погрешность соизмерима с величиной асимптоты, то считаем алгоритм неконечным.
3) задача решена.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827690
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В реальности имплементация алгоритма - будет наполнена побочными эффектами. Такими как
например
- попадание в кеши L2/L3
- наличие побочных эффектов многозадачности (Амдал и когеррентность)
- страничный кеш оперативной памяти
- резкое изменение отклика жёсткого диска в зависимости от нагрузки (близко к когеррентности)
- побочные эффекты рантайма (warmup) и управления памятью (фаза уборки мусора).

Они имеют более сложную (гистерезисную) природу и асимтотическая формула сложности
алгоритма как такового будет иметь бОльшую поправку. Грубо говоря вы просто увеличиваете
количество (n) и ожидаете к примеру логариму. Но на графике будет логарифма а потом - внезапный
скачок вверх (безо всякой видимой причины). И сколько ни смотрите на вашу формулу и алгоритм - там НИГДЕ
не будет видимого пояснения такого поведения.

Классическая машинка тьюринга не имела кешей L2/L3. Как вы будете их эффект учитывать - ума не приложу.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827693
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

1) требуем конечность алгоритма на всех допустимых входных данных.
если в требовании отказано, объявляем задачу о конечности алгоритмически неразрешимой
2) имея конечность алгоритма, делаем ряд тестов, определяем асимптоту и погрешность.
3) задача решена.

Я могу придумать алгоритм, на котором ваши тесты покажут неверный результат, о том и речь. Так как тесты проверят только конечное число входных данных. А сложность алгоритма связана с его поведением на бесконечности.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827695
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Все же, для больших входных данных, эффектом кэшей можно пренебречь. Возьмите имплементацию любого алгоритма сортировки, нарисуйте график зависимости времени от размера массива - начиная с некоторого n он будет соответствовать установленной теоретической сложности алгоритма.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827701
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonКак вы будете их эффект учитывать - ума не приложу.Практика показывает, что кэш ограничен, причем жутко ограничен и его легко перегрузить, тем самым нивелировать его эффект.

Но даже если речь пойдет про объемы входных данных соизмеримых с кэш, все равно погрешность не может превышать какие-то разумные пределы. Если оценка по времени будет в T, а погрешность даже в T/3, это перебор.

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

InterloperТак как тесты проверят только конечное число входных данных. А сложность алгоритма связана с его поведением на бесконечности.
Не стоит рассматривать недопустимые входные данные.
Если написано, что алгоритм принимает только конечные входные данные то смотрите сложность только в пределах допустимых входных данных. За пределами допустимых входных данных алгоритм следует считать неработающим (что есть равенство неконечности, а определение его сложности алгоритмически неразрешаемым). Тогда встает вопрос, зачем вообще оценивать алгоритм там, где он не работает?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827703
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin,

Можно написать алгоритм сортировки, который будет сортировать массив любого объема, помещающийся в памяти. Вы будете запускать тесты на всех возможных длинах массива? В таком случае, пока тесты завершатся, анализ будет уже никому не нужен.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827704
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Interlopermayton,

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

В этом случае сложность понятна, но время исполнения будет зависеть исключительно от входных данных.

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


В конце концов речь будет идти только о вероятностном поведении. А значит нужно найти такой алгоритм оценки, который бы оценивал лучше, чем погрешность оценки, этого будет достаточно с математической точки зрения. Если речь идет про неконечные (=непредсказуемые) алгоритмы, то достаточно будет доказать, что погрешность оценки соизмерима (или выше), чем время работы алгоритма, а значит с вероятностной точки зрения оценивать алгоритм будет нельзя (=невозможно). Опять же, это тоже результат.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827707
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperAklin,

Можно написать алгоритм сортировки, который будет сортировать массив любого объема, помещающийся в памяти. Вы будете запускать тесты на всех возможных длинах массива? В таком случае, пока тесты завершатся, анализ будет уже никому не нужен.

Мы говорим про оценку конечного алгоритма. Оценка конечная. Время на оценку конечное.
Время оценки у нас на одном конце линейки, а точность оценки (=погрешность) на другом. Уменьшая время на оценку увеличиваем погрешность.

Другими словами, нельзя сделать и быстро и дешево и качественно и одновременно.
А значит выбираем наиболее значимый параметр, и идем в его направлении.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827709
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin Если речь идет про неконечные (=непредсказуемые) алгоритмы, то достаточно будет доказать, что погрешность оценки соизмерима (или выше), чем время работы алгоритма, а значит с вероятностной точки зрения оценивать алгоритм будет нельзя (=невозможно).

Мы не можем вычислить заранее, что алгоритм неконечный. Это фундаментальное ограничение.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827710
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinInterloperAklin,

Можно написать алгоритм сортировки, который будет сортировать массив любого объема, помещающийся в памяти. Вы будете запускать тесты на всех возможных длинах массива? В таком случае, пока тесты завершатся, анализ будет уже никому не нужен.

Мы говорим про оценку конечного алгоритма. Оценка конечная. Время на оценку конечное.
Время оценки у нас на одном конце линейки, а точность оценки (=погрешность) на другом. Уменьшая время на оценку увеличиваем погрешность.

Другими словами, нельзя сделать и быстро и дешево и качественно и одновременно.
А значит выбираем наиболее значимый параметр, и идем в его направлении.

На скольких наборах входных данных вы будете тестировать алгоритм?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827712
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperВ чем путаюсь?
В постановке задачи. В первом посте вы написали про алгоритм, имеющий фиксированную сложность. А потом внезапно перешли к чёрному ящику, внутри которого Х алгоритмов, причём каждый со своей сложностью.

Interloperменя интересует общий случай.
Общий случай работает точно так же, только для каждого из Х вышеназванных алгоритмов выделяется диапазон и совпадение графиков проверяется отдельно на каждом из диапазонов.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827715
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Interlopermayton,

Все же, для больших входных данных, эффектом кэшей можно пренебречь. Возьмите имплементацию любого алгоритма сортировки, нарисуйте график зависимости времени от размера массива - начиная с некоторого n он будет соответствовать установленной теоретической сложности алгоритма.
Вы только что похоронили любую оптимизацию имплементации.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827720
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperМы не можем вычислить заранее, что алгоритм неконечный. Это фундаментальное ограничение.Но можем вычислить погрешность времени исполнения.
Если, как я выше писал, погрешность измерения выше соизмерима с временем исполнения, тогда алгоритм следует перевести в разряд неконечных.



InterloperНа скольких наборах входных данных вы будете тестировать алгоритм?А сколько у меня попыток для запуска?

Если у меня десять попыток, а входных данных может быть до миллиона, то сделаю по две попытки на 10, 100, 1000, 10000, 100000 и 1000000 элементов.
А потом посчитаю дельту между двумя запусками, о объявлю ее погрешностью

Если миллион попыток, а входных данных не больше 100, то можно по много раз перебрать все входные данные.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827742
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovInterloperВ чем путаюсь?
В постановке задачи. В первом посте вы написали про алгоритм, имеющий фиксированную сложность. А потом внезапно перешли к чёрному ящику, внутри которого Х алгоритмов, причём каждый со своей сложностью.

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

Возможно, действительно изложил сумбурно. Задача: анализировать алгоритмы, имеющие фиксированную сложность, но неизвестную нам, о которой мы можем лишь формулировать гипотезу.
В первом посте я писал, что мы можем просто замерять время выполнения на каждом тесте. Но пусть даже мы можем намного больше - анализировать исходный код алгоритма или его определение на машине Тьюринга. Оказывается, даже с таким расширенным инструментарием, точно проверить гипотезу о сложности невозможно.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827750
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovОбщий случай работает точно так же, только для каждого из Х вышеназванных алгоритмов выделяется диапазон и совпадение графиков проверяется отдельно на каждом из диапазонов.

В том-то и дело, что нет способа выбрать диапазон, достаточный для проверки. А проверять на всем диапазоне тупо перебором нецелесообразно - это займет намного больше времени, чем практическая эксплуатация алгоритма. Более того, даже если вы проверите алгоритм на всех возможных вариантах для конкретного объема памяти на вашей машине, алгоритм на машине с большим объемом памяти может вести себя по иному. Вот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другой, и далее меняться не будет. То есть как бы вы не замеряли алгоритм на своей машине, вы не получите правильный результат.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827754
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinInterloperНа скольких наборах входных данных вы будете тестировать алгоритм?А сколько у меня попыток для запуска?

Если у меня десять попыток, а входных данных может быть до миллиона, то сделаю по две попытки на 10, 100, 1000, 10000, 100000 и 1000000 элементов.
А потом посчитаю дельту между двумя запусками, о объявлю ее погрешностью

Если миллион попыток, а входных данных не больше 100, то можно по много раз перебрать все входные данные.

Ни на каком конечном наборе данных нельзя сделать вывод о сложности алгоритма. Что именно вам непонятно в этом утверждении?

Смотрите объяснение выше, в котором я объясняю что даже полным перебором вариантов на конкретном компьютере нельзя оценить сложность алгоритма.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827768
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperВот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другойВообще никак не бьётся с (выделено мною):InterloperЗадача: анализировать алгоритмы, имеющие фиксированную сложность , но неизвестную нам, о которой мы можем лишь формулировать гипотезу.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827922
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Interloperточно проверить гипотезу о сложности невозможноЕсли есть алгоритм, исходник, в котором нет рандома, то возможно.

Для начала ищем места, которые могут зависнуть алгоритм. Если такие есть, то задача решена (ибо доказательство неконечности тоже результат).

Если алгоритм не зависает, то делаем простое аппроксимирование, ну или ассиптоту ищем в заданной погрешности.

InterloperНи на каком конечном наборе данных нельзя сделать вывод о сложности алгоритма. Что именно вам непонятно в этом утверждении?Алгоритм, тем более конкретная программа не может быть определена на бесконечном объеме данных. А раз она определена только на конечном объеме данных, то достаточно искать примеры в этом объеме. Их может быть немало, но этот список все равно конечен.
Вопрос тот же: если алгоритм работает на N элементах T времени, то нужно будет не менее чем T*log(N)*log(N) запусков для грубой оценки, это в сферических условиях в вакууме. Наличие любого стремного фактора можно сразу умножать на десять. T можно определить, как можно и определить конечность алгоритма, имея его исходник на понятном языке (в данном случае математически идеальная машина Тьюринга является малопонятной). Еще встает вопрос о конечности самого исходника. Время, требуемое для анализа алгоритма будет также зависеть от размера исходника.

В общем, если все размеры определены, то потребуется что-то вроде A*B*C*D*E... = X времени для оценки.

InterloperСмотрите объяснение выше, в котором я объясняю что даже полным перебором вариантов на конкретном компьютере нельзя оценить сложность алгоритма.
Там идет жонглирование понятиями. Сначала утверждается что алгоритм конечен, а потом идет попытка выдать конечный алгоритм за бесконечно долгий. Не стоит этого делать.

Нужно делить мух и котлет. Найдите условия конечности, а неконечные алгоритмы сразу в мусорку с пометкой "нерешаемо".
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827929
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovInterloperВот прямо специально его возьмут и запрограммируют так, что для входных данных объемом меньше N (причем N не влезет в вашу доступную память) сложность алгоритма будет такой, а для входных данных больше N - сложность будет другойВообще никак не бьётся с (выделено мною):InterloperЗадача: анализировать алгоритмы, имеющие фиксированную сложность , но неизвестную нам, о которой мы можем лишь формулировать гипотезу.

Вообще нет противоречия. Сложность не может быть фиксированной или нефиксированной, она одна. Это теоретический концепт, говорить о котором можно только с точки зрения асимптотики. Еще раз: сложность нельзя проверить на конечном числе входных данных, сколько бы данных вы не взяли.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827933
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinInterloperточно проверить гипотезу о сложности невозможноЕсли есть алгоритм, исходник, в котором нет рандома, то возможно.

Для начала ищем места, которые могут зависнуть алгоритм. Если такие есть, то задача решена (ибо доказательство неконечности тоже результат).

Невозможно даже для агоритмов без рандома.
Места, в которых может зависнуть алгоритм, нельзя найти программно.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827934
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinАлгоритм, тем более конкретная программа не может быть определена на бесконечном объеме данных. А раз она определена только на конечном объеме данных, то достаточно искать примеры в этом объеме. Их может быть немало, но этот список все равно конечен.
И сразу ошибка. Алгоритм может быть определен на неограниченном объеме данных. Алгоритм сортировки может сортировать массивы любой размерности, лишь бы они умещались в памяти.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827936
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinТам идет жонглирование понятиями. Сначала утверждается что алгоритм конечен, а потом идет попытка выдать конечный алгоритм за бесконечно долгий. Не стоит этого делать.

Если вы что-то не поняли, не стоит сразу называть это жонглированием. Там не было речи о бесконечно долгом алгоритме.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827938
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinВопрос тот же: если алгоритм работает на N элементах T времени, то нужно будет не менее чем T*log(N)*log(N) запусков для грубой оценки, это в сферических условиях в вакууме. Наличие любого стремного фактора можно сразу умножать на десять. T можно определить, как можно и определить конечность алгоритма, имея его исходник на понятном языке (в данном случае математически идеальная машина Тьюринга является малопонятной). Еще встает вопрос о конечности самого исходника. Время, требуемое для анализа алгоритма будет также зависеть от размера исходника.

В общем, если все размеры определены, то потребуется что-то вроде A*B*C*D*E... = X времени для оценки.

1. Конечность алгоритма определить невозможно (см. неразрешимость проблемы останова)
2. Какое бы N не взять, можно проанализировать только сложность алгоритма на промежутке от 1 до N, но не сложность всего алгоритма, который определен для любого N.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827942
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperМеста, в которых может зависнуть алгоритм, нельзя найти программно.Вы явно не знакомы с методиками тестирования и верификации =)


InterloperИ сразу ошибка. Алгоритм может быть определен на неограниченном объеме данных. Алгоритм сортировки может сортировать массивы любой размерности, лишь бы они умещались в памяти.Объем памяти на реальном компьютере ограничен.


Interloper1. Конечность алгоритма определить невозможно (см. неразрешимость проблемы останова)С определенной вероятностью возможно.

Вопрос лишь в объеме ресурсов. Нельзя определить конечность алгоритма если объем ресурсов на определение меньше. чем объем ресурсов на использование этого алгоритма.
В некоторых других случаях можно (особенно имея исходник).


Interloper2. Какое бы N не взять, можно проанализировать только сложность алгоритма на промежутке от 1 до N, но не сложность всего алгоритма, который определен для любого N.Я правильно понимаю, что вы говорите, например при N=3 мы можем определить конечность алгоритма при N=1, N=2 и N=3, а для других целых 0 < N <= 3 определить не можете ?

Начните с утверждения, что алгоритм протестирован. и дальше либо подтвердите его, определив конечную сложность, либо опровергните.

Если же речь про сферические в вакууме алгоритмы, не используемые на практике, то задача должна звучать иначе.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827949
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Топик закончится только после того, как мы все дружно восхитимся ТээСовым "открытием".
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827982
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
зачем вообще это все. есть алгоритм, есть его оценка. что тут происходит? алгоритм раскраски? коммивояжера? нет? ну тогда зачем?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827983
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить , верно ли предположение о сложности?

фигня какая. это в самом алгоритме. чо там проверять
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827985
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinОбъем памяти на реальном компьютере ограничен.
На конкретном - да. Но можно найти компьютер с большим объемом памяти, чем на том, на котором запускаем тесты.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827986
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinВопрос лишь в объеме ресурсов. Нельзя определить конечность алгоритма если объем ресурсов на определение меньше. чем объем ресурсов на использование этого алгоритма.
В некоторых других случаях можно (особенно имея исходник).

Если найдете способ как, сразу получите Нобелевку, не меньше.
В каких некоторых случаях? Для алгоритма суммы чисел? Тогда да.
Может имеет смысл сначала разобраться в вопросе вместо того, чтобы упрямо гнуть свою линию, ничем не подкрепляя?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827989
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinЯ правильно понимаю, что вы говорите, например при N=3 мы можем определить конечность алгоритма при N=1, N=2 и N=3, а для других целых 0 < N <= 3 определить не можете ?

Неправильно. Вы можете протестировать алгоритм для N от 1 до 3. Допустим, он выполнился за 1, 2, 3 мс. Вы сделали вывод, что алгоритм работает за линейное время. Но если запустить алгоритм на следующих N, то можно увидеть, что алгоритм выполняется за квадратичное время, и дальше это не меняется, следовательно, сложность алгоритма - O(n^2).

Пример такого алгоритма:

int TestAlg(int n) {
int s = 0;

for (int i = 0; i < 3; ++i) s += 1;

for (int i = 3; i < n; ++i)
for (int j = 0; j < n; ++j) s += 1;

return s;
}

Только пусть вместо 3 в качестве граничной точки будет какое-то очень большое число, которое вы не превысите своими тестами.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39827990
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bachInterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить , верно ли предположение о сложности?

фигня какая. это в самом алгоритме. чо там проверять

Если в алгоритме тысячи строк, "глазами" оценить сложность не получится.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828052
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить, верно ли предположение о сложности?зачем это проверять? особенно с учётом возможной переменной асимптотики.
Обычная практическая задача в CS: проверяют\доказывают конечность реализации алгоритма, т.е. лимит времени на конкретном железе на крайних условиях. А задача по доказательству асимптотики алгоритма лежит обычно на алгоритмистах\математиках.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828053
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperНа конкретном - да. Но можно найти компьютер с большим объемом памяти, чем на том, на котором запускаем тесты.Любое конечное большое число памяти всегда много меньше, чем бесконечное.
"много меньше" это значит, что даже если ты помножишь этот объем памяти сам на себя хоть тысячу раз подряд, все равно будет меньше.
Это школьный уровень алгебры и начал анализа.


InterloperМожет имеет смысл сначала разобраться в вопросе вместо того, чтобы упрямо гнуть свою линию, ничем не подкрепляя?Вам тот же совет =)


InterloperНо если запустить алгоритм на следующих NВ рамках задачи, где алгоритм определен для любого целого N <= 3 нельзя запускать этот алгоритм для любого N > 3.
Это другая задача, которую на практике не решают (точнее решают программисты-теоретики или программисты-верификаторы, а не то, чем мы здесь занимаемся).

Опять вернулись к тому, что вы ставите в условие конечность алгоритма, а потом требуете определить его работоспособность за пределами условий. А когда вам отвечают, что это не удолевтворяет условиям задачи, либо же говорят, что это невозможно - вы сразу со своей несвязанной и неверной теорией лезите про "общий случай при заранее известных конечных условиях". Нет никаких общих случаев, если есть заданные условия.



InterloperЕсли в алгоритме тысячи строк, "глазами" оценить сложность не получится.Это значит алгоритм нечитаемый, а значит он неконечный может быть.
Исходим из условий читаемости алгоритма, его исходника.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828065
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperМы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить, верно ли предположение о сложности?Это взаимоисключающие вещи: сделать много замеров и формально доказать. Для формального доказательства есть специальные инструменты, например, Isabelle HOL . Вот, статьи:

https://arxiv.org/pdf/1802.01336.pdf
https://github.com/bzhan/Imperative_HOL_Time
https://pdfs.semanticscholar.org/610c/ab44732605e05a2cc6359bfc47ae76260654.pdf

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

Сложность алгоритмов доказывать ещё сложнее. Есть отдельный класс алгоритмов: разделяй и властвуй . Он упоминается в статьях выше, для них описываются методы доказательства.

Если реально хочется формально доказать, то, на это уйдет порядка полугода. Месяца через 2-3 вы только начнете понимать самые базовые вещи в формальных доказательствах. У меня, например, на эту штуку ушло 1,5 года.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828074
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если нужно оценивать сложность произвольного алгоритма и полностью формальное доказательство не нужно, то я бы сделал анализатор выражений. Для начала тупо искал бы в AST циклы, потом добавил анализ использования переменных циклов, чтобы отслеживать такие ситуации:

Код: c#
1.
for (int i = 0; i < 100; i+=2) { i--; }


Потом добавил анализ рекурсивных вызовов. И дальше по мере поступления новых алгоритмов усложнял анализ.

На выходе анализатора можно выдавать две вещи:
1) примерную оценку
2) какие-нибудь граничные значения переменных, которые использовал бы при запуске алгоритма, чтобы посчитать реальное время выполнения

Затем сравнивал бы оценку и то, что получается по результатам запуска. Если есть расхождения, то выдаём предупреждение. И такие алгоритмы оцениваем уже китайским методом: арендуем подвальчик с сотней китайцев. Они анализируют алгоритм и дорабатывают оцениватель. Хотя не обязательно подвальчик, можно запилить какой-нибудь сайт или мобильную игру "Оцени сложность алгоритма".


Кстати, есть безумная идея. Можно сделать алго-валюту (a la крипто-валюта). Только если в криптовалютах деньги даются тупо за вычисление хеша. То в алго-валюте деньги будут выдаваться за более эффективную реализацию алгоритмических задачек. Скажем один участник отправляет в p2p-сеть алгоритмическую задачку, минимальные требуемые критерии (например, максимальная сложность, объем памяти и т.п.) и какую-то сумму реальных денег. Другие участники отправляют свои реализации алгоритма. 1-ый чел, который отправил алгоритм, который удовлетворяет минимальным условиям, получает допустим 1/e или 1/pi от исходной суммы. 2-ой чел, который отправит алгоритм лучше 1-го получит 1/e от оставшейся суммы и т.д.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828076
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, одним из обязательных требований к реализации алгоритма может быть наличие формального доказательства сложности. Если оно нужно, то чел донатит штуку баксов и люди потом сидят полгода доказывают. Или быстрее, если они гении математики.

Interloper, короче, всё, другого общего решения у этой задачки нет. Нужно делать алго-валюту, инфа 100%.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828094
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinЛюбое конечное большое число памяти всегда много меньше, чем бесконечное.
"много меньше" это значит, что даже если ты помножишь этот объем памяти сам на себя хоть тысячу раз подряд, все равно будет меньше.
Конечное число памяти позволяет проверить алгоритм только на конечном наборе данных.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828096
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinНо если запустить алгоритм на следующих NВ рамках задачи, где алгоритм определен для любого целого N <= 3 нельзя запускать этот алгоритм для любого N > 3.
[/quot]
В рамках задачи алгоритм определен для любого целого N. Это у вас есть памяти столько, что вы можете проверить алгоритм только для значений N<=3, что не даст правильно оценить сложность алгоритма.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828101
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinОпять вернулись к тому, что вы ставите в условие конечность алгоритма, а потом требуете определить его работоспособность за пределами условий.

Вы путаете конечность алгоритма в смысле того, что он заканчивается за конечное число шагов, и конечность множества допустимых входных данных. Алгоритм "сумма двух чисел" конечен, но на вход ему могут быть поданы сколь угодно большие числа и их бесконечно много.

AklinА когда вам отвечают, что это не удолевтворяет условиям задачи, либо же говорят, что это невозможно - вы сразу со своей несвязанной и неверной теорией лезите про "общий случай при заранее известных конечных условиях". Нет никаких общих случаев, если есть заданные условия.
Если вы не понимаете теорию, это не делает ее неверной и несвязной. Что касается общих случаев: я указал в постановке задачи, что интерес представляет общий случай, универсальный алгоритм.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828264
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperКонечное число памяти позволяет проверить алгоритм только на конечном наборе данных.
Если вопрос стоит о проверке алгоритма на объеме памяти большем, чем есть на этом компьютере, значит эту задачу на этом компьютере решать нельзя. Не пытайтесь ложкой прокопать тоннель под Ла-Маншем. Для начала обзаведитесь техникой.


InterloperВ рамках задачи алгоритм определен для любого целого N. Это у вас есть памяти столько, что вы можете проверить алгоритм только для значений N<=3, что не даст правильно оценить сложность алгоритма.Тот же ответ: если памяти не хватает, то _НЕЛЬЗЯ_ определять. Можно переформулировать условия задачи для N <= 3, тогда можно. А иначе нельзя. Это уже другая задача.

Тут вопрос простой, я выше писал. МОжно ли запустить алгоритм с массивом N > 3 на компьютере с памятью N <= 3 и при этом алгоритм не упадет? Ответ: не выйдет, алгоритм упадет (будет читать ошибочные данные и т.п.), то есть алгоритм неработоспособный. А значит мы простыми методами доказали на практике неработоспособность алгоритма, задача решена. Алгоритм отправляется разработчикам для правок (чтобы на компьютере с памятью N <= 3 можно было загружать данные N > 3). А пока этого не сделано, у нас готовый ответ: алгоритм не работает.

Зачем определять сложность неработающего алгоритма я не понимаю.


InterloperВы путаете конечность алгоритма в смысле того, что он заканчивается за конечное число шагов, и конечность множества допустимых входных данных. Алгоритм "сумма двух чисел" конечен, но на вход ему могут быть поданы сколь угодно большие числа и их бесконечно много.
В линуксе есть генератор случайных чисел, чтение из которого никогда не заканчивается. Сделаем проще. Запустим алгоритм читать из этого генератора число размером больше, чем оперативная память. А когда алгоритм упадет по причине нехватки памяти объявим, что алгоритм неработоспособный и оценка его сложности невозможна. Задача решена.



Мысль по-прежнему кристально чиста:
1) определить, что алгоритм конечен на данном компьютере для всех допустимых входных комбинаций (это вопрос к верификации). если это по каким-либо причинам, вне зависимости от причин, не может быть реализовано, то принимаем сложность равную "минус один", что идентично "алгоритм завис или упал".
2) определить асимптоту и погрешность. если погрешность относительно мала, то ответ найден. Если велика, то принимаем сложность алгоритма как "минус два", что идентично "сложность алгоритма случайна".
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828267
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А если задача стоит определить сложность не запуская алгоритм на компьютере, то это совсем иные методы.

Но начинать все равно придется с определения конечности.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828344
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinЗачем определять сложность неработающего алгоритма я не понимаю.


Алгоритм работает. Но на вашем конкретном компьютере он имеет предельно допустимый набор возможных входных данных. На другом компьютере будет другой. Оценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении, так как для этого нужно знать, как алгоритм ведет себя при неограниченном увеличении N.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828345
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinНо начинать все равно придется с определения конечности.
Что вы понимаете под конечностью?
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828375
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperОценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении
Сможем. Это называется "экстраполяция" и является результатом решения задачи аппроксимации набора значений некоторой функцией.

Поэтому возвращаемся к первому ответу: получаем столько пар (N,t) сколько не надоест, строим по ним график из точек, аппроксимируем их разными функциями, смотрим в какую функцию он укладывается лучше всего. Эту функцию и объявляем сложностью данного алгоритма.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828423
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

Существуют алгоритмы, для которых такой способ будет давать неверное решение. Пример приводил выше. Так можно и рандомно выбирать сложность и объявлять ее ответом. Точное решение либо есть, либо его нет. Для данной задачи - нет и в принципе быть не может.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828461
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperДля данной задачи - нет и в принципе быть не может.
Как скажете, сэр.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828544
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperАлгоритм работает.Это не доказано.


InterloperОценивая алгоритм только на своем компьютере, вы не сможете сделать вывод о его асимптотическом поведении
А вы не сможете оценить его на всех компьютерах планеты, а значит, даже имея линейны алгоритм, состоящий из одного цикла, вы не можете говорить с вероятностью даже близкой к 50%, что у него сложность линейная, ведь это не так.

Другими словами, в вашем "общем случае, мы действительно не можем определить сложность нерабоющего алгоритма хотя бы потому, что он не работает".


InterloperAklinНо начинать все равно придется с определения конечности.
Что вы понимаете под конечностью?
Конечный объем входных данных на конечном ограниченном числе машин с конечным ограниченным числом параметров, и при этом на этих условиях алгоритм работает конечное время, не превышающее заданное.

Если это не так, то алгоритм нуждается в доработке.


Dimitry SibiryakovПоэтому возвращаемся к первому ответу: получаем столько пар (N,t) сколько не надоест, строим по ним график из точек, аппроксимируем их разными функциями, смотрим в какую функцию он укладывается лучше всего. Эту функцию и объявляем сложностью данного алгоритма.Если верить ТС, не выйдет, потому что нужно построить график для таких N, которые ни один компьютер в мире запустить не сможет.
InterloperТочное решение либо есть, либо его нет. Для данной задачи - нет и в принципе быть не может.Для неточной задачи не может быть точного решения.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828548
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinЕсли верить ТС, не выйдет, потому что нужно построить график для таких N, которые ни один компьютер в мире запустить не сможет.
Да, да, я уже понял, что слова "аппроксимация" и "экстраполяция" для него пустое сотрясение воздуха, недостойное открытия гугля.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828634
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

Постановка задачи требует точного ответа, аппроксимация здесь неуместна. Аппроксимировать можно, что угодно, но задача не звучит как "аппроксимируйте сложность алгоритма".
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828635
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinКонечный объем входных данных на конечном ограниченном числе машин с конечным ограниченным числом параметров, и при этом на этих условиях алгоритм работает конечное время, не превышающее заданное.

Конечность алгоритма никак не связана с выходными данными и машинами.
Алгоритм сортировки - конечен. Работает с массивами сколь угодно большой длины.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828636
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinДругими словами, в вашем "общем случае, мы действительно не можем определить сложность нерабоющего алгоритма хотя бы потому, что он не работает".

В общем случае мы не можем определить сложность рабочего алгоритма, потому что эта задача эквивалентна алгоритмически неразрешимой задаче определении того, закончит ли произвольный алгоритм работу за конечное число шагов. Если вы не верите, что такая задача неразрешима, теория алгоритмов в помощь.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828666
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Завершаемость определить проще. Для функциональных языков, где единственный источник незавершаемости - это рекурсия, это делается так.

1) Для всех аргументов определена мера. Для числовых аргументов - это обычно просто значение числа. Для строковых - это может быть длина строки или ещё что-то. Для алгебраических типов данных - это обычно количество конструкторов в выражении. Например для "Cons 4 (Cons 2 Nil)" размер может быть равен 3. Аналогично вычисляется размер деревьев (количество узлов) и т.п.

Для таких простых типов мера обычно определяется автоматически. Для более сложных её приходится определять вручную. Например, мне здесь пришлось определить такую меру:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
primrec size_type :: "'a type => nat" where
  "size_type OclSuper = 0"
| "size_type (Required t) = 0"
| "size_type (Optional t) = 0"
| "size_type (Collection t) = Suc (size_type t)"
| "size_type (Set t) = Suc (size_type t)"
| "size_type (OrderedSet t) = Suc (size_type t)"
| "size_type (Bag t) = Suc (size_type t)"
| "size_type (Sequence t) = Suc (size_type t)"
| "size_type (Tuple t) = Suc (ffold tcf 0 (fset_of_fmap (fmmap size_type t)))"



2) По умолчанию тот же Isabelle HOL пытается найти аргумент или комбинацию аргументов функции, которые с каждым шагом рекурсии уменьшаются. Обычно этого достаточно.

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

Код: sql
1.
2.
3.
termination
  by (relation "measure (&#955;(xs, ys). size ys)";
      auto simp add: elem_le_ffold' fmran'I)



А здесь (раздел 4.1) есть хороший пример почему автоматическое доказательство завершаемости может не работать:

Код: sql
1.
2.
function sum :: "nat => nat => nat" where
"sum i N = (if i > N then 0 else i + sum (Suc i) N)"



Эта функция вычисляет сумму 1+2+...+N

Аргумент i с каждым шагом увеличивается на 1, а аргумент N остается неизменным. Поэтому они определяют меру N - i, которая с каждым шагом уменьшается. И ещё добавляют 1, видимо потому, что на последнем вызове рекурсии i > N. При этом N - i будет всё-равно 0, потому что это натуральные числа, а не целые. И если не добавить 1, то на двух последних шагах мера будет 0 - оставаться неизменной, а должна уменьшаться.

Код: sql
1.
2.
3.
4.
termination sum
apply (relation "measure (&#955;(i,N). N + 1 - i)")
apply auto
done





Для императивных языков доказательство завершаемости должно быть сложнее, потому что там есть переменные, значения которых могут изменяться не только при рекурсивных вызовах, но просто по ходу выполнения алгоритма. Но общая идея там должна быть такая же:

1) Определяем источники незавершаемости. Тут кроме рекурсивных вызовов это могут быть циклы и функции из стандартной библиотеки! Кстати функции из стандартной библиотеки могут ещё и влиять на сложность алгоритма: поиск в массиве, в хеше и т.п.

2) Определяем простые правила для определения завершаемости (например, один из аргументов или их комбинация всегда уменьшаются или, например, переменная цикла только уменьшается/увеличивается пока не доходит до конечного значения).

3) Для сложных ситуаций всё-равно пользователю придется определять кастомную меру. Кстати, эта мера может быть обязательной частью алгоритма. Чел, который написал алгоритм, пусть прикладывает и меру.

4) Самая жесть - это интегрировать всё это с какой-нибудь системой автоматического доказательства теорем. Обычно это сводится к тому, что нужно реализовать этот язык программирования (на котором пишутся алгоритмы) в Isabelle HOL или ещё какой-то системе. Для Isabelle HOL есть какая-то реализация Java, какие-то примеры простых абстрактных императивных языков. Я, например, реализовывал язык OCL . Причём, там только абстрактный синтаксис, система типов, правила типизации выражений, без семантики. Для того же C# или другого языка нужно либо искать готовую реализацию, либо это тема для докторской диссертации на несколько лет.



Короче, сделать всё полностью формально очень сложно. Если это требуется, то проще всего, чтобы люди, которые пишут алгоритмы, писали их сразу на нормальном языке типа Isabelle HOL, который поддерживает автоматизированные доказательства теорем. При этом сами и доказывали бы завершаемость, сложность и т.п. Либо можно использовать языки, которые легко интегрируются с такими системами. Для Scala вроде было что-то такое.

Если формальное доказательство не нужно. А просто запускать алгоритм много раз - это слишком тупо. То нужны какие-то эвристики. Например, парсим функцию, получаем её абстрактное синтаксическое дерево (во многих языках это поддерживается). И анализируем циклы, рекурсивные вызовы и т.п. Затем подтверждаем полученную оценку запуском алгоритма на разных входных данных. С практической точки зрения это самое простое и реальное, что можно сделать. На мой взгляд такая штука была бы очень прикольной и востребованной. Например, есть PVS Studio, которая не может формально доказать корректность программы, но в ней заложено много эвристик, которые находят типовые ошибки. С практической точки зрения это уже не плохо. Аналогично и ваша штука могла бы примерно оценивать сложность алгоритмов.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828676
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ares_ekb,

попробуй ради интереса доказать так O(N) для алгоритма составления бинарной кучи
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828725
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperПостановка задачи требует точного ответаНельзя сделать точный ответ в неточных условиях.


InterloperКонечность алгоритма никак не связана с выходными данными и машинами.
Алгоритм сортировки - конечен. Работает с массивами сколь угодно большой длины.
Пока нет гарантий что алгоритм вообще работает и выдает верный ответ - оценивать его бесполезно.


InterloperВ общем случае мы не можем определить сложность рабочего алгоритма, потому что эта задача эквивалентна алгоритмически неразрешимой задаче определении того, закончит ли произвольный алгоритм работу за конечное число шагов. Если вы не верите, что такая задача неразрешима, теория алгоритмов в помощь.
Ты снова пытаешься получить ТОЧНЫЙ Ответ на задачу без условия.
Так не выйдет.
Сделай условие. Сделай границы работы. И тестируй.
Если же вопрос про ТЕОРЕТИЧЕСКУЮ сложность - это вопрос анализа структуры кода, не более чем. Объем данных тут роли не играет. Это сугубо теоретическая оценка, не привязанная ни к чему. Для этой оценки не нужно запускать этот алгоритм даже один раз.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828757
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinЗачем определять сложность неработающего алгоритма я не понимаюЗатем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения. Таких вы ни в чём не убедите, поздравьте с открытием, и прения прекратятся. Лично я поздравляю!

З.Ы. Может кто недопонимает неразрешимость массовой алг-й пр-мы. Это не возможность решить задачу в принципе, а невозможность составить один такой алгоритм для всех частных случаев.
Я не уверен, что ТС сам это до конца понимает.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828783
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperПостановка задачи требует точного ответа
Не может быть у этой задачи точного ответа, поскольку так называемая "сложность алгоритма" - не точная величина, а всего лишь грубая оценка. Она не может быть применена для вычисления времени работы алгоритма на заданном объёме данных.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828796
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98Затем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения.Я так понял, что ТС хочет определить некую сложность для сферического в вакууме и нигде не описанного алгоритма в общем виде. Алгоритм-то в общем виде, а вот сложность должна быть точной величиной.

Забавно в общем.

А чем дальше тем веселее: раз для ряда алгоритмов сложность нельзя определить потому что алгоритмы не могут завершиться, то значит это правило ТС растягивает на все алгоритмы без исключения, делая заранее придуманный им вывод, со ссылками на несвязанные статьи.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828807
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovInterloperПостановка задачи требует точного ответа
Не может быть у этой задачи точного ответа, поскольку так называемая "сложность алгоритма" - не точная величина, а всего лишь грубая оценка. Она не может быть применена для вычисления времени работы алгоритма на заданном объёме данных.
Да эта теоретическая оценка может очень сильно отличаться.
И мы даже не сможем придумать никакой поправочный коэффициент. Поскольку тут дело будет даже не в коэффициенте.
Вобщем простая многослойная нейронная сеть автору в помощь и наверное удастся экспериментально подобрать кривую
похожую на фактический отклик алгоритма.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828918
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklinexp98Затем, что это сферический алгоритм, да ещё и в ваккууме. Такова идэ фикс ТСа. Причём, в задаче нет ни теоретического, ни практического значения.Я так понял, что ТС хочет определить некую сложность для сферического в вакууме и нигде не описанного алгоритма в общем виде. Алгоритм-то в общем виде, а вот сложность должна быть точной величиной.

Забавно в общем.

А чем дальше тем веселее: раз для ряда алгоритмов сложность нельзя определить потому что алгоритмы не могут завершиться, то значит это правило ТС растягивает на все алгоритмы без исключения, делая заранее придуманный им вывод, со ссылками на несвязанные статьи.

Сложность должна быть не точной величиной, а указанием на один из классов сложности. Но в целом вы почти меня поняли: так как не существует универсального алгоритма для определения факта остановки любого алгоритма, то и не существует универсального алгоритма для проверки сложности, иначе этот алгоритм может быть преобразован в алгоритм определения факта остановки.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828919
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ares_ekb,

Интересно, изучу ваши выкладки на досуге, спасибо.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828921
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperСложность должна быть не точной величиной, а указанием на один из классов сложности.

Interloperтак как не существует универсального алгоритма для определения факта остановки любого алгоритма
Не существует алгоритма для оценки неработающего алгоритма в виде черного ящика.

Для работающего алгоритма с исходниками алгоритм определения сложности придумать несложно, он будет прост, тем более, что есть множество испытанных практических методов, описанных выше.


InterloperСложность должна быть не точной величиной, а указанием на один из классов сложности.Это сугубо теоретический вопрос тогда, а не вопрос программирования.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828941
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А ещё я тугодум и так и не понял
автор...алгоритма для проверки сложности, иначе этот алгоритм может быть преобразован в алгоритм определения факта остановки Для нас доказали теорему о неразрешимости массовой проблемы останова.
Проверка сложности является частным случаем алгоритма проверки останова. Для этого ч-го случая мне лично не приходилось видеть признанных доказательств неразр-ти.
Кроме того,не приходилось видеть и док-в того, что если неразрешима массовая проблема, то неразр-ма и частная проблема.

Тем не менее нам здесь пытались втюхать, что она верна по причине того, что является ч-м случ-м алгоритма проверки останова и потому верна. Т.о., налицо неправомерное применение "доказательства от противного", т.е. весьма противное доказательство. И прежде всего я протестовал против этого, поскольку все другие рассуждения были достаточно очевидны.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828947
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinНе существует алгоритма для оценки неработающего алгоритма в виде черного ящика.

Слова "неработающего" и "в виде черного ящика" уберите, а так все верно. С чего вы выдумали, что речь идет о неработающих алгоритмах - ума не приложу.
Что касается вида, то он может быть любой, хоть исходный код. Не исходный код какого-то одного конкретного алгоритма: алгоритм оценки должен принимать на вход исходный код любого алгоритма. Для частного случая в виде подмножества алгоритмов, решение, безусловно существует.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828948
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AklinЭто сугубо теоретический вопрос тогда, а не вопрос программирования.
Это вопрос теории алгоритмов, естественно, а не того программирования, которым вы занимаетесь в офисе.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828949
Interloper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98Для этого ч-го случая мне лично не приходилось видеть признанных доказательств неразр-ти.
.
Доказательство приведено в этой теме на 2й странице. Оно достаточно простое, чтобы в нем мог разобраться любой, кто знает основные понятия математической логики.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828961
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)попробуй ради интереса доказать так O(N) для алгоритма составления бинарной кучи
Чтобы доказать формально нужно время. Интересная идея, я попробую, если будет возможность. Но на это уйдет наверное неделя-две, потому что я никогда таким не занимался.

А с помощью эвристик это можно сделать так:

Алгоритм выглядит следующим образом (по ссылке ещё есть ссылка на прикольную книгу, где всё описано более подробно "Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ"):
Код: sql
1.
2.
3.
4.
Build_Heap(A)
  A.heap_size = A.length
  for i = floor(A.length/2) downto 1
    do Heapify(A, i)

где A - это входной массив, который нужно превратить в кучу
A.length - его длина (которая равна длине кучи A.heap_size и для простоты мы эту длину будем иногда обозначать просто N)
Heapify - это функция, которая упорядочивает элементы в поддереве кучи:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Heapify(A, i)
  left = 2i
  right = 2i+1
  largest = i
  if left <= A.heap_size и A[left] > A[largest]
    then largest = left
  if right <= A.heap_size и A[right] > A[largest]
    then largest = right
  if largest != i
    then Обменять A[i] и A[largest]
         Heapify(A, largest)



Допустим этот алгоритм написан на каком-то реальном ЯП, а не псевдоязыке. Мы распарсили его и получили абстрактное синтаксическое дерево (AST), которое будем анализировать.

Сначала оценим сложность функции Heapify:

Видим в AST этой функции рекурсивный вызов себя. Других рекурсивных вызовов или циклов нет, значит сложность определяется этим единственным вызовом. При рекурсивном вызове передаются 2 аргумента: A и largest. Аргумент A в теле функции никак не изменяется и передаётся как есть. Для largest возможны 3 варианта:

1) largest = i, в этом случае рекурсия прекращается
2) largest = 2i
3) largest = 2i+1

Короче анализатор AST должен сделать такие выводы:
1) С каждым рекурсивным вызовом i как минимум удваивается.
2) Рекурсия прекращается в худшем случае когда i достигает A.heap_size (для простоты будем называть её N)

В wiki и в книге из этого делается неправильный вывод, что сложность этой функции равна O(log N). Наш же анализатор должен сделать вывод, что сложность равна O(log N) - O(log i) или просто O(log N/i). Где log - логарифм по основанию 2. Попробую пояснить почему так.

Например есть цикл:
Код: sql
1.
for (int x = i; x < N; x += step) { ... }

Для него сложность будет O((N-i)/step). Если i=0 и step = 1, то это вырождается просто в O(N).

Для такого цикла:
Код: sql
1.
for (int x = i; x < N; x *= step) { ... }

Сложность будет O(log_step(N/i)), где log_step - логарифм по основанию step.

Функция Heapify эквивалентна как-раз такому циклу со step = 2.


Теперь оцениваем сложность Build_Heap. Видим в ней цикл от floor(N/2) до 1 с шагом 1. Сложность цикла равна
O(sum_i (сложность тела цикла)) =
O(sum_i (log N/i)) =
O(sum_i (log N) - sum_i (log i)) =
(раскрываем сумму по i от 1 до N/2)
O(N/2 * log N - log (N/2)!) =
(тут мы используем тот факт , что O(log N!) = O(N log N))
O(N/2 * log N - N/2 * log (N/2)) =
O(N/2 * log (N / N/2)) =
O(N/2 * log 2) =
(отбрасываем константы)
O(N)

Готово!


Чтобы все эти вычисления автоматизировать нужно:
1) Заложить все эти эвристики по анализу for, if, рекурсивных вызовов и т.п. в абстрактных синтаксических деревьях
2) Нужна какая-то система, которая упрощает O-выражения - это выглядит вполне реальным. Возможно подойдут готовые системы для символьных вычислений или можно самому что-то написать.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39828967
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Идея всего этого такая... В книге приводится какое-то очень не тривиальное доказательство сложности O(N). Там делается утверждение
Поскольку число вершин высоты h в куче из n элементов не превышает ceil(n / 2^(h+1)), а высота всей кучи не превышает floor(lg n), то время работы не превышаети дальше приводится какая-то безумная формула.

Автоматизировать такие рассуждения невозможно. А ту последовательность действий, которую я привёл выше, вполне можно автоматизировать.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829011
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Насчет формальных доказательств. Нашёл очень клёвую реализацию некоторого абстрактного императивного языка IMP2 для Isabelle HOL. В нём есть переменные, циклы, условия и т.п. Ещё можно задавать разные инварианты для императивных программ, которые можно доказывать. И ещё для этого языка буквально неделю назад запилили реализацию двоичной кучи как-раз по книге Кормена Т. и др. "Алгоритмы: построение и анализ". Там доказывается корректность этой реализации.

Причём реализация двоичной кучи занимает по идее 1 страницу, а доказательств там больше чем на 20 страниц. И это даже без доказательства сложности алгоритма. Это показывает на сколько всё сложно с формальными методами. На практике для произвольных алгоритмов реально использовать только какие-то эвристики, которые описывал выше.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829032
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ares_ekb,

да, в математическом доказательстве используется сходящаяся геометрическая прогрессия - тынц
И это очень простой пример, без подкавык.
По многим алгоритмам используется оптимистичная оценка, например: хэш-таблица, декартово дерево

Судя по всему, даже со специализированным языком "с подсказками" и частично работающее, в общем виде реально тянет на RocketScience
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829033
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ares_ekbНасчет формальных доказательств. Нашёл очень клёвую реализацию некоторого абстрактного императивного языка IMP2 для Isabelle HOL. В нём есть переменные, циклы, условия и т.п. Ещё можно задавать разные инварианты для императивных программ, которые можно доказывать. И ещё для этого языка буквально неделю назад запилили реализацию двоичной кучи как-раз по книге Кормена Т. и др. "Алгоритмы: построение и анализ". Там доказывается корректность этой реализации.

Причём реализация двоичной кучи занимает по идее 1 страницу, а доказательств там больше чем на 20 страниц. И это даже без доказательства сложности алгоритма. Это показывает на сколько всё сложно с формальными методами. На практике для произвольных алгоритмов реально использовать только какие-то эвристики, которые описывал выше.я так подозреваю, что если ты не НАСА, то платить программистам за такую разработку явно перебор :-)
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829138
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperAklin
Слова "неработающего" и "в виде черного ящика" уберите, а так все верно. С чего вы выдумали, что речь идет о неработающих алгоритмах - ума не приложу.
Что касается вида, то он может быть любой, хоть исходный код. Не исходный код какого-то одного конкретного алгоритма: алгоритм оценки должен принимать на вход исходный код любого алгоритма. Для частного случая в виде подмножества алгоритмов, решение, безусловно существует.С того, что его разработчик не может гарантировать конечность времени исполнения этого алгоритма на допустимых входных данных.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829139
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperAklinЭто сугубо теоретический вопрос тогда, а не вопрос программирования.
Это вопрос теории алгоритмов, естественно, а не того программирования, которым вы занимаетесь в офисе.Тогда речь не может идти о том, что на компьютере не хватит памяти, или вообще о количестве запусков.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829193
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
InterloperСложность должна быть не точной величиной, а указанием на один из классов сложности.
Тогда вспоминай матан (если, конечно, для тебя это слово не матерное). Степенная функция отличается от линейной и логарифмической. Причём для их различения достаточно трёх точек.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829197
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovПричём для их различения достаточно трёх точек.В указанных ТС пределах делать замеры нельзя, ибо функция может потенциально зависнуть.

А если она "может" то зависнет.
А если зависнет, то встает вопрос об алгоритмически невозможном определении конечности этого алгоритма, а это известная доказанная проблема, поэтому даже пытаться не стоит =)

А доказывать математически он не хочет.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829261
Ares_ekb
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)да, в математическом доказательстве используется сходящаяся геометрическая прогрессия - тынц

И это очень простой пример, без подкавык.Проблема таких доказательств как по ссылке в том, что их невозможно автоматизировать. Там очень много рассуждений, каких-то посылок, которые берутся просто из головы автора и никак не следуют из структуры алгоритма. Например, откуда взялась эта лемма "Пусть для какого-то элемента массива при вызове siftdown было сделано i вызовов оператора swap. Тогда его индекс не превосходил floor(n/2^i)"? Ни один инструмент точно не сможет сформулировать и доказать такую лемму из ниоткуда.

Чтобы можно было оценивать сложность автоматически, нужно свести эту процедуру к каким-то очень простым шагам. Пусть этих шагов будет очень много, пусть там будет много тупого перебора, но зато это можно автоматизировать.

Насчет подкавык. Вполне возможно, что для человека какое-то доказательство будет сложным, а для тупого машинного перебора - простым. Или наоборот.

kealon(Ruslan)Судя по всему, даже со специализированным языком "с подсказками" и частично работающее, в общем виде реально тянет на RocketScienceЕсли полностью формальное доказательство, то да. А если какие-то полуформализованные эвристики по анализу кода, как я описывал, то вполне реально сделать. Хотя даже это вполне потянуло бы на диссертацию :)
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39829526
vas0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если взять просто быструю сортировку Хоара (QuickSort). Сложность в худшем n^2. Сложность в среднем n*log, да и то сложность в среднем оценивается лишь вероятностно.

Доказательство сложности в среднем даже зная алгоритм непростая задача. А для черного ящика видимо и вообще мрак. Если "опорный элемент" для хоара будет случайно выбираться, уже с оценкой будешь иметь проблему: иногда n*log, а иногда n^2.

Оценка по сложности это скорее подсказка, чтобы не попасть с проклятием размерности, а не точная величина.
...
Рейтинг: 0 / 0
Верификация сложности алгоритма
    #39836576
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Interlopermaytonпропущено...

Твои уточняющие вопросы напоминают легкий троллинг отвечающих.
Тебе уже в первом ответе дали методику.

Ты ее применил? Ты нарисовал график в Excel?

Давай дружище сделай как советуют опытные. А потом подойдешь к теории снова.

График меня не интересует. Я уже понял, что проблема алгоритмически неразрешима.
Вопрос я задал фундаментальный, решение тупо взять нарисовать график, очевидно, не решает поставленную задачу.
InterloperПредположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить, верно ли предположение о сложности?

Программно проверить? Напишите программу, если хотите программно проверить. Одним из параметров будет функция подозрительная на асимптотику, проведите ряд экспериментов по n, постройте отношение затраченного времени черного ящика и ф. подозрительной на асимптотику, если функция та самая, то в пределе получите константу. Что там как вы говорите алгоритмически неразрешимого? Вам по-моему о чем-то подобном говорили
...
Рейтинг: 0 / 0
118 сообщений из 118, показаны все 5 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Верификация сложности алгоритма
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]