Разделяй и властвуй. Повышение эффективности алгоритмов. Часть 2

[Pochemuk]

Очень интересный подход. Позволяет формализовать оценку временной сложности без досконального анализа алгоритма.

Но вот такой вопрос: какова область применимости? Любой ли алгоритм, использующий деление, можно им оценить (например, сортировку Хоара)? Можно ли "натянуть" его на алгоритмы, в которых разделения не являются постоянными и пересекаются в разные моменты времени (сортировки Шелла и "расческой")?

[java_prog]

Не поручусь за любой, но уверен сортировку Хоара можно изложить. Чуть позже подготовлю и добавлю абзац с этим алгоритмом

[Pochemuk]

Кроме алгоритма Штрассена существуют и другие более эффективные алгоритмы умножения матриц, основанные на рекурсивном делении на более мелкие матрицы. Как насчет них?