Привет. Пусть у нас есть XML-ник, без особой экзотики в своей структуре. То есть - равномерно заполненный такой XML-ник, N нодов, log(N) глубиной. Какая будет средняя по больнице сложность XPath-запросов в нем? Речь именно о сложности относительно N / log(N) (количества нодов / глубины). Понятно, что сложность будет как минимум линейной от числа топ-левел нодов, захваченных запросом. В моем случае юзается libxml2, вопрос возник в связи с желанием понять, следует ли разбивать XML-ник на части, если известно, что со временем он станет очень большой. Сам же XML-ник грузится один раз, и один раз под него создается XPath-контекст. То есть весь вопрос - именно о сложности отработки единичного запроса.
