InterloperAklin,

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


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


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

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

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


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

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

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



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

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

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

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

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

InterloperВерно. Если алгоритм при увеличении n, начиная с определенного n выполняется за конечное константное время, то его сложность O(1) <= O(nlogn).
ММм... может и так, но к нашей задачи это отношения все равно не имеет.


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

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




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


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

Алгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

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

AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

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

поправка*

AklinАлгоритм нахождения алгоритма для данной задачи оценки сложности алгоритма:

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

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

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

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

InterloperТак как тесты проверят только конечное число входных данных. А сложность алгоритма связана с его поведением на бесконечности.
Не стоит рассматривать недопустимые входные данные.
Если написано, что алгоритм принимает только конечные входные данные то смотрите сложность только в пределах допустимых входных данных. За пределами допустимых входных данных алгоритм следует считать неработающим (что есть равенство неконечности, а определение его сложности алгоритмически неразрешаемым). Тогда встает вопрос, зачем вообще оценивать алгоритм там, где он не работает?

Interlopermayton,

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

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

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


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

InterloperAklin,

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

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

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