Алгоритм практического определения сложности алгоритма

Выписать попугаи бенчмарка (число тиков/операций) для 10, 100, 1000 ... 100000 элементов.

Выписать гипотезы:

тиков/элементов = 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.

а это уже подстава...

Моя задача про максимальный сегмент после удаления элемента...

Моё решение o(n log n). Предыдущая попытка была отвергнута как timed out... Вторая попытка (практически тот же текст):

Runtime: 1874 ms, faster than 100.00% of Rust online submissions for Maximum Segment Sum After Removals.

Memory Usage: 6.1 MB, less than 100.00% of Rust online submissions for Maximum Segment Sum After Removals.

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

Моё решение: хранить сегменты в BTree, при удалении элемента вынимать сегмент и вставлять на его место два.

Максимум хранится в BTree в виде размер сегмента: количество сегментов с таким размером.

При удалении сегмента, его размер удаляется из дерева сегментов (или делает -1). При добавлении - либо вставляется, либо делает (+1).

Максимум из Btree находится за n log n. Решение - n log n амортизированное, n^2 - worst case (на который я наткнулся в бенчмарке - удалять элементы по-очереди).
 
... А вот теберь я готов пойти читать про finger tree, и может быть, я открою для себя что-то новое.


UPD: Даже сравнить не с чем:

Accepted Solutions Runtime Distribution

Sorry. We do not have enough accepted submissions to show distribution chart.

Accepted Solutions Memory Distribution

Sorry. We do not have enough accepted submissions to show distribution chart.

А теперь пятиминутка унижения: есть решение за O(n) в примерно 10 строк.

Вздох... Но я пытался.