Экзотические функции, почхаммер и красно-чёрные деревья

Question

Рассмотрим изначально пустое RB-дерево, в которое мы вставляем m элементов. Вставка элемента занимает O (log n) времени, где n - текущее количество вставленных элементов. Таким образом, я могу записать общее время m вставок, как: log (i) для i = 1..m == log (Pochhammer (1, m); любезно предоставлено WolframAlpha.

Действительно, соотношение m * logm и log (Pochhammer (1, m) сходится к 1, поэтому, я думаю, именно поэтому я нигде раньше не видел log - Pochhammer.

Какие еще «экзотические» функции используются в информатике? Я знаю, что в Union-Find и т. Д. Появляется inverse-ackerman ...

Answer 1

Гипергеометрические функции (которые вы можете назвать "экзотическими") часто встречаются в математике. Причина в том, что по определению их ряды Тейлора имеют простую форму. Поэтому они появляются, как только вы используете индукцию.

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

Также здесь, конечно, sum (log k) = log (prod k) = log k !, так что вам даже не нужны фантастические вещи. Тот факт, что вы получаете символ Pochhammer, вероятно, происходит от метода суммирования символьных рядов Mathematica. Смотри например. для алгоритма Цайльбергера, который суммирует ряды с использованием гипергеометрических функций.