Та же идея применима к спискам с пропусками, если ограничить высоту списка двойкой. В этом случае легко показать, что оптимальным является расстановка узлов высоты два как раз через n^1/2 узлов нижнего уровня. Это гарантирует время поиска в списке порядка O(n^1/2). Более точно это время оценивается, как 2n^1/2. Идею можно развить, если ввести не два уровня, а например, три. Тогда оптимальным будет расположение «высоких» узлов через n^1/3 узлов каждого уровня. Этот даст нам время поиска порядка 3n^1/3. Если довести эти рассуждения до логического конца, то при k=log₂n уровнях (в этом случае получаются минимально возможные подмассивы длины два) получим время поиска равное 2log₂n — это кмк оптимальный результат полноценного списка с пропусками. И подозреваю, что такое же время будет у нормального дерева отрезков…

Дополнительная память не нужна для хранения элементов массива, но она используется для организации вычислений… А насчет стека загляните на страницу 217, упражнение 7.4

Последний раз повторяю, для тех, кто в танке (:
1) Стек нужен в любой реализации быстрой сортировки — если вам не нравится Седжвик, то загляните в Кормена (там C/С++ нет).
2) Хвостовой рекурсии в быстрой сортировке нет, т. к. в ней имеется два рекурсивных вызова. В том же Кормене есть упражнение, в котором описывается как избавиться только от одного рекурсивного вызова (при этом размер стека все равно в лучшем случае будет равен log(n)…

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

> К примеру, мне интересно, а зачем нужна память в быстрой сортировке?

Для хранения стека…

Есть ли повторяющиеся символы в ASCII-строке длиной в 336 символов? Да! И для этого не надо просматривать всю строку… :)

ОК

Насколько мне помнится, и без приоритетов тоже эквивалентны универсальной машине Тьюринга.

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

Почему бы не перебрать все варианты, т.е. не делать алгоритм вероятностным

Я по этому поводу общался с человеком, входящим в мембранное братство, у нас не получилось превзойти линейно-логарифмическое время, не вводя тех самых доп. условий — приоритета или поляризации.

Я бы правила-схемы 3-5 в одно объединил

Есть такой вариант! Но мне нравятся бинарные отношения :)

Надо будет поиграться с этой идеей… Хотя, как я заметил, для распараллеливания, чем алгоритм проще, тем лучше!

Уговорили! :) Кстати, интересно, а что, если пространство, в котором мы собираемся реализовать предложенный алгоритм, будет бесконечномерным? :)

Спасибо большое за ссылку, почитаю на досуге…

Есть немного :)

Мембранный он просто потому, что реализован в рамках мембраной модели, а так (почти) обычный алгоритм полного перебора. Был бы рад (без подколок) услышать от Вас описание лучшего алгоритма!

ОК, время от получения условий задачи до его решения — полиномиально, а общее время, затраченное на решение (например, в мембрано-часах) — экспоненциально… :)

А что, есть шанс? :)

А что Вы скажете о колонии бактерий, размер которой увеличивается по экспоненте? Просто они делают это (делятся) одновременно, не используя никаких общих ресурсов (память, энергия и т.д.), по крайней мере на начальном этапе роста… :)

Кстати, верное соображение! Хотя в первых работах по данной тематике рассматривались такие «мощные» операции, как деление мембран сразу на n частей — вот там-то получить линейное время вполне по силам. Правда, такая модель становится еще дальше от своего биологического прототипа…

Вещь! :)

Является-является! :) Так как NP-полнота задача определяется не по времени ее решения, а скорее, наоборот: если задача NP-полная, то ее решение на любом последовательном вычислителе потребует экспоненциального времени.

И в этой аналогии что-то есть! Буду думать… :)