![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoВыписать попугаи бенчмарка (число тиков/операций) для 10, 100, 1000 ... 100000 элементов.
Выписать гипотезы:
тиков/элементов = O(n)
тиков/(элементов*элементов) = O(n2)
тиков/(элементов * ln(элементов) = O(n*log n)
А дальше смотрится на колонку с результатом, какой ближе всего похож. Например, у меня получилась такая колонка результатов:
Видно, что сходится к 1.86 (10000 и 100000 элементов). Увы, это колонка из квадратичной сложности.
(Более того, насколько я знаю, примерно так сложность алгоритма определяется и в теоретическом смысле - смотрится, какая функция его ограничивает сверху/снизу в пределе). Тут мы отношения в пределе заменяем просто практическими наблюдениями.
(И да, я всё ещё не закончил с max-segments). Оказывается, я ошибся в основной части алгоритма, а не в сложности хранения максимумов. Я заменил все операции с максимумами на тривиальные, и сложность не поменялась...
... упс, это у меня бенчмарк случайно сделал worst case. При random картинка меняется... У меня получается, чистый n log n.
Выписать гипотезы:
тиков/элементов = O(n)
тиков/(элементов*элементов) = O(n2)
тиков/(элементов * ln(элементов) = O(n*log n)
А дальше смотрится на колонку с результатом, какой ближе всего похож. Например, у меня получилась такая колонка результатов:
| 195.5 |
| 15.8081 |
| 3.006889 |
| 1.86123681 |
| 1.82581181 |
Видно, что сходится к 1.86 (10000 и 100000 элементов). Увы, это колонка из квадратичной сложности.
(Более того, насколько я знаю, примерно так сложность алгоритма определяется и в теоретическом смысле - смотрится, какая функция его ограничивает сверху/снизу в пределе). Тут мы отношения в пределе заменяем просто практическими наблюдениями.
(И да, я всё ещё не закончил с max-segments). Оказывается, я ошибся в основной части алгоритма, а не в сложности хранения максимумов. Я заменил все операции с максимумами на тривиальные, и сложность не поменялась...
... упс, это у меня бенчмарк случайно сделал worst case. При random картинка меняется... У меня получается, чистый n log n.
no subject
Date: 2022-12-05 02:04 pm (UTC)Упражнение: Определить сложность алгоритма определения сложности алгоритма.
no subject
Date: 2022-12-05 02:34 pm (UTC)С учётом времени выполнения целевого алгоритма или без? Впрочем, полагая сложность изучаемого алгоритма S, а так же то, что алгоритм не diverge, то сложность получается C*S, где C - не очень большая константа (фиксированного набора предположений и фиксированного количества прогонов целевой программы с разным набором данных).