1
При изучении Master theorem У меня возникла проблема с реализацией алгоритма реального мира в качестве примера, стратегия повторения которого упадет на Case 3. Можете ли вы предложить какие-либо ссылки, где я могу больше узнать о таких алгоритмах?Пример основной теоремы 3 Примеры алгоритмов
Благодарим вас за предложение. Проблема заключается в том, что теорема Мастера может быть применена только к QuickSelect, когда вы выбираете опорный элемент детерминированным способом: f.e. всегда медиана. Проблема в том, что вы не можете сделать это на практике, потому что вам понадобится QuickSelect, чтобы найти его в первую очередь. Если вы выберете опорную точку Median Of Medians, вы не сможете использовать теорему Учителя об этом. У вас есть другой, более «строгий» пример? – oskopek