OpenGL:
Что ты понимаешь под сложностью алгоритма, если не количество действий, нужных для его выполнения?

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833326

Wound:
Ну как нет, если да. Покажи где экспонентная сложность в той функции? Там линейная сложность.



Так сложнее или экспоненциальный?

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833325

Qraizer: Нет. Даже если рассматривать её рекурсивный алгоритм, она не требует более одного шага на каждый шаг рекурсии. Пример с хабра требует двух шагов. Тот факт, что второй шаг по факту вырожден, не играет качественной роли, алгоритм всё равно остаётся сложнее полиномиального. Количественно же он не требует большего объёма ресурсов.
Тонкая грань, да. Как "задача" и "метод". ;)

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833324

Wound:
В каком месте он экспоненциальный? Тогда функция advance - тоже имеет экспоненциальную сложность?

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833323

vot:
Те же мехрнизмы могут быть задействованы и на других типах движков.
Так что дело не в типе движка, а в его функциональных возможностях!

https://forum.sources.ru/index.php?showtopic=418954&view=findpost&p=3833322

Андрей Игонин: Крутая игра кст

https://forum.sources.ru/index.php?showtopic=415081&view=findpost&p=3833321

Qraizer: Неприятно, да, OpenGL? Эх, математики…
Алгоритм всё равно остался экспоненциальным, полиномиальным он будет, например, в такой форме:
Только вы забыли, что сложность алгоритма – это качественное понятие,а не количественное.

Добавлено 27.06.20, 13:26
В данном случае количественной разницы нет.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833320

Wound: Он просто спутал массив и число(даже 5-ти и даже миллион знаковое число - это ведь одно неделимое целое - число), ну ничего, ну бывает так. Я представляю реакцию людей на хабре, теперь ставится ясно почему он им правду донести не может.

Добавлено 27.06.20, 12:38

Длина входных данных для числа равно всегда 1, если не указано явно иное.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833319

Qraizer:

https://forum.sources.ru/index.php?showtopic=419071&view=findpost&p=3833318

swf: Ой... кажется, я лажанулась.
Я говорю о задаче ДП, а не о методе ДП.
Ну у меня почти 2 ночи.
Из Котова:

Метод! Не задача ДП, а метод ДП.
Почему-то думала, что этот метод называется мемоизация, когда в табличке что-то запоминаем.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833262

OpenGL:
Ты мне льстишь :)
Значит я тебя просто не так понял. Если ты согласна с тем, что в статье ДП, то предмета для спора нет.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833261

swf: У математиков не принято якать. "Мы решаем" - стандартный оборот речи.
И немножко убавьте свой тон. Мы (вы и я) ведём академическую дискуссию.
Это первое.
Теперь второе. Я нигде не говорила, что в статье необычные примеры.
Более того, я сказала, что эти примеры очень напоминают примеры из лекций Котова по ДП для школьников.
Пожалуйста, внимательно читайте мои сообщения.

И, наконец, третье и самое интересное.
Если вы считаете, что задача ДП - это не задача оптимизации, а задача подсчёта сущностей, дайте ссылку.
Безотносительно ДП, как вообще определяется "задача подсчёта сущностей"? Например, с точки зрения теории алгоритмов.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833260

esperanto: вестник смерти

https://forum.sources.ru/index.php?showtopic=418813&view=findpost&p=3833259

Jin X: А на ВМ проц типа стартует сразу с разогнанной частоты, поэтому и показывает её?

Добавлено 26.06.20, 19:59
Я в том году поинтереснее код для теста начал писать, но не доделал. Хотя, осталось чуть-чуть.
Я вот только думаю, есть ли смысл выравнивать тестовый код по 16 байтам?
Как я понял, основная фишка этого выравнивания в том, чтобы весь код попал в один 16-байтный блок. Т.е. если код занимает, скажем, 8 байт (ну или 24), то он может начинаться с любого адреса от 0 до 7 (в младшем полубайте), разницы не будет никакой.

update: Вот инфа по этому поводу. Получается, что так и есть.
code_align.png (, : 1)

https://forum.sources.ru/index.php?showtopic=419072&view=findpost&p=3833257

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

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833256

swf: А что тогда означает фраза решить задачу:
а) линейным программированием;
б) квадратичным программированием;
в) выпуклым программированием;
г) целочисленным программированием;
д) нелинейным программированием;
е) математическим программированием ?
:D
Мы решаем задачу оптимизации, которая имеет собственное математическое определение.
В случае ДП задача ДП - задача, которая обладает вышеперечисленными свойствами + ещё одно, которое там пропущено: что и состояния, и управления зависят от конечного числа параметров.
А формулируется она (задача)так: Найти допустимое управление такое, чтобы целевая функция была максимальна/минимальна.
И ни слова больше. Как чего и кого мы разбиваем, в табличке, на коленке или ещё как - наше сугубо личное дело.
Решить задачу - среди всех допустимых управлений найти максимизирующее/минимизирующее ЦФ.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833255

JoeUser:
Отчасти ты прав. Но многие наверное забыли мат.статистику ... :) Простой пример. У нас есть эмпирическая выборка из 1000 величин. По сути - выборка:

1) Означает какое-то влияние
2) У этого влияния есть какой-то коэффициент
3) У эмпирически собранных данных есть разброс - это де факто

Но есть еще и Ситуация Йопта) когда по какой-то причине сбиваются вычисления/отсчеты.

Напомню, как поступают бородатые дядьки... в плане их собственной "нормализации"

1) Все величины сортирют
2) Начинают отсекать "экстремумы". Для этого делят весь отрезок на 4 части. Из частей 2-3 получают либо среднне, либо средне-квадратичное
3) Из отрезков 1 и 4 начинают удалять значения, которые по модулю разности меньше вычлененных значений и удаляемых более, чем в два раза
4) Если число усечений справа и слева не превышает 20-25% - получают верный коэффициент влияния
5) Если не получилось - или повторяют, или утверждают, что эксперимент носит вааще никакую детерминированность (типа искать не тут, давайде другие данные)

Спрашивается а при чем тут "милисекунды"? А они просто - часть эксперимента. Запустив 1000 раз одно и то же здание в реальных условиях (загружжености компа, незагруженности) - мы выйдем к "СРЕДНЕМУ". По методе, как я описал выше. Коэффициент какойта! Как назвать, сами считайте - скорости, мощности, офигительности ...

https://forum.sources.ru/index.php?showtopic=419018&view=findpost&p=3833254

OpenGL:
Я не знаю, что это такое. Фраза "решить задачу динамическим программированием" на практике всегда означает её сведение к меньшей задаче и вывод рекуррентных соотношений, а не вот это вот всё.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833253

core-i7:
не совсем так..
Чтобы получить реальное время, нужно иметь счётчик и частоту, на которой этот счётчик работает. Например если взять счётчик процессора TSC и разделить его не на частоту процессора, а частоту таймера HPET, то получим не правильное время. Именно поэтому пара QPC+QPF должны всегда ходить вместе. Если замерить, сколько раз простучит QPC в течении одной секунды, то непременно получим значение, которое вернёт нам QPF. Это-же касается и пары RDTSC+CPUfreq.


да.. он кривой, т.к. я его набросал на коленке. Спасибо вот Jin X поправил. ;)


я имел в виду, что индусы точили набор функций NtCreateProfile(), с которыми я кстати так и разобрался до конца.


вполне возможно, только эта частота у меня всегда совпадает с физической частотой системной шины, без множителя CPU.


именно так он и работает!
На новых чипсетах TSC выделен в отдельный домен, и идёт напрямую от системного клокера, - овер биоса на неё не влияет.
tscp.png (, : 5)

https://forum.sources.ru/index.php?showtopic=419072&view=findpost&p=3833252

swf:
Вот что там в комментах написано

ДП у комментатора решает задачи снизу вверх. А если не снизу вверх, то это уже не ДП.

Определения ДП в сообщении (не будем называть учебные тексты статьями) нет.
Вот есть хорошая книжка по ДП для школьников-олимпиадников, лекции Котова,
там такой же подход (задача - подзадачи - правильные рекуррентные соотношения) и похожие примеры с последовательностями.
Но это не определение ДП.
Вот определение:


Добавлено 26.06.20, 18:19
Аддитивность или мультипликативность ЦФ, конечно.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833251