Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
 Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Предположим, у нас есть программно реализованный алгоритм, решающий некую задачу. Предполагается, что этот алгоритм имеет определенную сложность, выраженную нотацией "О большое", например, O(n*logn). Мы можем вызывать алгоритм на разных входных данных и замерять время его выполнения.
Как программно проверить, верно ли предположение о сложности?
17 июн 19, 12:31    [21909660]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 58146
плавно увеличивать N и замерять время работы алгоритма в различных попугаях ?

100-120-144-172-207...-1000000000000
17 июн 19, 12:40    [21909670]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Aklin
плавно увеличивать N и замерять время работы алгоритма в различных попугаях ?

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


И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?
17 июн 19, 13:36    [21909732]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 58146
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?
Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности.
17 июн 19, 13:38    [21909733]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
График, построенные по результатам эксперимента, должен совпасть с графиком, построенным на теоретических данных, с заданной точностью.
17 июн 19, 13:38    [21909734]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Aklin
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?
Постройте два графика: получившийся и предполагаемый. Сделайте сравнение в пределах погрешности.


Насколько большое N нужно брать для графика?
17 июн 19, 13:43    [21909736]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 58146
Interloper
Насколько большое N нужно брать для графика?
Зависит от того, под какие данные рассчитан алгоритм.

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

Просто бывают алгоритмы, к примеру тех же сортировок, рассчитанных на сортировку малых массивов, скажем, до 20 элементов. И гонять такой алгоритм даже на 100 элементах уже кощунство.
17 июн 19, 13:50    [21909743]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Aklin
Interloper
Насколько большое N нужно брать для графика?
Зависит от того, под какие данные рассчитан алгоритм.

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

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


В том то и дело, что мы не знаем как устроен алгоритм внутри.
Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.
17 июн 19, 13:54    [21909748]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
x1ca4064
Member

Откуда:
Сообщений: 1003
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?


Делить время на сложность - должно асимптотически приближать к некоторой константе, т.е. Время/(n*log(n)), для Вашего примера.
17 июн 19, 13:57    [21909753]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 58146
Interloper
В том то и дело, что мы не знаем как устроен алгоритм внутри.

Если у алгоритма нет генератора случайных чисел в виде одного из параметров "работы", то пройдитесь от 1 до 2^K, каждый раз увеличивая размер чисел вдвое. Делая несколько замеров на каждом N, с разными входными данными. Верхний предел - простое любопытство, время, при котором компьютер будет гонять алгоритм достаточно продолжительное для вашего ожидания время. В некоторых случаях это могут и быть и сутки, но для простых замеров достаточно, чтобы алгоритм работал одну-две минуты.

Если есть генератор случайных чисел и он определяет сложность, и погрешность при этом велика, то никак вы не определите, что там внутри. Для одних и тех же данных время может различаться, либо различаться не на одних и тех же, а скажем на соседних данных (с точки зрения алгоритма). Например, 2+2 будет складываться одну минуту, а 2+3 уже пятнадцать минут.
17 июн 19, 13:58    [21909754]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Aklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.
17 июн 19, 14:20    [21909778]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
x1ca4064
Interloper
И как понять, что получившаяся последовательность замеров действительно соответствует предполагаемой сложности?


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


Каков алгоритм проверки на асимптотическое приближение?
17 июн 19, 14:20    [21909780]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Interloper
Aklin,

Генератор случайных чисел не обязателен. Это может быть банальное ветвление логики в зависимости от входных данных. Природа алгоритма неизвестна. Мы должны придумать универсальное решение или показать, что его не существует.
Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.
17 июн 19, 14:56    [21909822]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
x1ca4064
Member

Откуда:
Сообщений: 1003
Interloper

Каков алгоритм проверки на асимптотическое приближение?


Я бы попробовал метод наименьших квадратов для линейного приближения: если угол наклона стремится к 0, значит приближаемся к асимптоте.
17 июн 19, 14:56    [21909824]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Barlone
Interloper
Aklin,

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


Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.
17 июн 19, 14:58    [21909832]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
x1ca4064
Interloper
Каков алгоритм проверки на асимптотическое приближение?


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


Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?
17 июн 19, 15:00    [21909833]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
x1ca4064
Member

Откуда:
Сообщений: 1003
Interloper

Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?


У Вас есть набор точек Y=(Время)/(Сложность) от X=(Сложность), после МНК получим:
Y=a*X+b, если a мало (внешний задаваемый параметр, означет точность нашего диагноза), значит (Время)=O(Сложность)
17 июн 19, 15:06    [21909844]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Interloper
Barlone
пропущено...
Кому мы должны? Понятно, что если неизвестно, что там внутри, то мы не можем даже быть уверенны, что алгоритм, дважды запущенный на одних и тех же данных, выполнится за одинаковое время. Или что из ста запусков на одних данных 99 раз выполнится за секунду, а сотый раз за час.


Внесу уточнение: алгоритм является детерминированным и завершается за конечное время на любых входных данных.
А вам с какой целью? Успешная проверка на некотором наборе вариантов не будет являться доказательством вашего предположения. Если конечно это не полный перебор всех возможных вариантов входных данных.
17 июн 19, 15:07    [21909848]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Barlone
Interloper
пропущено...


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


Мне чисто из интереса.
17 июн 19, 15:09    [21909851]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
x1ca4064
Interloper
Наклона чего по отношению к чему? Как будем оценивать стремление к нулю?


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


МНК даст нам оценку отклонения нашей функции от некоторой эталонной. Какую считать эталонной для O(N*N)? Нам то неизвестны коэффициенты, "спрятанные" внутри О большое.
17 июн 19, 15:12    [21909858]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Если чисто из интереса, то непонятна претензия:
Interloper
Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.

В любом случае, у программной реализации есть ограничения на входные данные: какое количество данных помещается в память, помещаются ли сами значения в используемый тип...
17 июн 19, 15:15    [21909861]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Если алгоритм работает с каким-то массивом, то константа про О большом будет меняться в момент, когда массив перестанет помещаться в кеш.
17 июн 19, 15:22    [21909871]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Barlone
Если чисто из интереса, то непонятна претензия:
Interloper
Для N<1000000 он может вести себя как линейный, затем начинает вести себя как квадратичный.
Так что такой принцип решения не годится.

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

Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.
17 июн 19, 15:24    [21909872]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Interloper
Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.
Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.
17 июн 19, 15:34    [21909878]     Ответить | Цитировать Сообщить модератору
 Re: Верификация сложности алгоритма  [new]
Interloper
Member

Откуда: Москва
Сообщений: 488
Barlone
Interloper
Чисто из интереса не означает ограничение общности. Предложенное решение "строить график от 1 до какого-то конкретного N" неверно в общем случае, о чем я и написал.
Считаем, что у нас бесконечно много памяти, чтобы вместить любые входные данные.
Для практического применения вполне нормально. А для теоретических рассуждений о бесконечной памяти и бесконечном времени - нужно и перебор вести до бесконечности.


То есть такой проверяющий алгоритм не существует?
17 июн 19, 15:47    [21909894]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить