Версия сайта для слабовидящих
Санкт-Петербургская классическая гимназия №610
школаучебалюдипартнерыдосугфотобанкфорум
             

Форум

новое сообщение | поиск | статистика | правила | регистрация

Григорий Ярославцев: Можно по простому // 19 ноября 2007, 00:04

В задаче про знаменитость можно просить не решение за O(N) времени, а решение, использующее не более K * N обращений к элементам матрицы в худшем случае (например 3 * N - я за столько умею). Это вполне понятно.

Комментировать | Вся дискуссия
учитель Сергей Чистович: Ага, вариант. // 21 ноября 2007, 15:11

Только зачем три? Хватит и двух, кажется.

Комментировать
Григорий Ярославцев: [без темы] // 21 ноября 2007, 23:11

Я не искал меньшую константу из идеологических соображений: пусть нам предложили ответ - тогда на его проверку необходимо 2 * (N - 1) операций, а успеть найти кандидата в ответы быстрее, чем за O(N) в худшем случае довольно странно. При этом эти две задачи скорее всего не перекрываются, так что 3 показалось мне похожим на нижнюю оценку для константы. В общем, интересно было бы в пятницу услышать решение за 2 * N =)

Комментировать

«Бывают люди, которым знание латыни не мешает все-таки быть ослами»

М. Сервантес,
испанский писатель