#algorithm #analysis
#алгоритм #анализ #оценка #степенной закон
Вопрос:
Эта проблема основана на головоломке Джоэла Спольски от 2001 года.
Парень «получает работу уличного художника, рисуя пунктирные линии посередине дороги».В первый день он заканчивает 300 ярдов, во второй — 150, а на 3-й и того меньше. Босс в ярости и требует объяснений.
«Я ничего не могу с этим поделать», — говорит парень. «С каждым днем я все дальше и дальше удаляюсь от банки с краской!»
Мой вопрос в том, можете ли вы оценить расстояние, которое он преодолел за 3-й день?
Один из комментариев в связанной теме действительно выводит точное решение, но мой вопрос касается достаточно хорошей оценки — скажем, 10% — которую легко сделать из общих принципов.
уточнение: речь идет об определенном методе анализа алгоритмов, а не о разработке алгоритма или кода.
Ответ №1:
Здесь много неизвестных — его скорость ходьбы, скорость рисования, как долго держится краска на кисти…
Но очевидно, что здесь происходят два процесса. Один из них квадратичный — это перемещение туда и обратно между банкой с краской и точкой рисования. Другой является линейным — это сам процесс рисования.
Думая о 10-м или даже 100-м дне, становится ясно, что линейная составляющая становится незначительной, и процесс становится почти квадратичным — ходьба занимает почти все время. Напротив, в течение первых нескольких минут первого дня он близок к линейному.
Таким образом, мы можем сказать, что время t как функция расстояния s следует степенному закону t ~ s ^ a с изменяющимся коэффициентом a = 1,0 … 2,0. Это также означает, что s ~ t ^ b, b = 1 / a.
Применение эмпирических порядков анализа роста:
Коэффициент b между днем 1 и днем 2 аппроксимируется как
b(1,2) = log (450/300) / log 2 = 0.585 ;; and so,
a(1,2) = 1/b(1,2) = 1/0.585 = 1.71
Как и ожидалось, a коэффициент ниже 2. Переходя к периоду времени между днем 2 и днем 3, мы можем установить его примерно на среднее значение между 1,71 и 2,0,
a(2,3) = 1.85 ;; a = 1.0 .... 2.0
b(2,3) = 0.54 ;; b = 1.0 .... 0.5
s(3) = s(2) * (3/2)^b(2,3)
= 450 * (3/2)^0.54
= 560 yards
Таким образом, расстояние, пройденное за третий день, можно оценить в 560 - 450 = 110 ярдах.
Что, если коэффициент a уже имеет максимально возможное значение 2.0 (что невозможно)? Затем 450*(3/2)^0.5 = 551 ярды. И для другой крайности, если бы это было то же самое 1.71 (чего, очевидно, тоже не может быть), 450*(3/2)^0.585 = 570 .
Это означает, что оценка в 110 ярдов правдоподобна, с ошибкой менее 10 ярдов с каждой стороны.
Ответ №2:
учитывая четыре предположения :-
painting speed = infinity
walking speed = x
he can paint only infinitly small in one brush stroke.
he leaves his can at starting point.
The distance he walks for painting dy road at y distance = 2y
Total distance he walks = intgeration of 2y*dy = y^2 = y^2
Total time he can paint y distance = y^2/x
Time taken to paint 300 yards = 1 day
(300)^2/x = 1
x = 90000 yards/day
Total time he can paint distance y = y^2/90000
(y/300)^2 = 2 after second day
y = 300*2^(1/2) = 424
Day 1 = 300
Day 2 = 424-300 = 124
Day 3 = 300*3^(1/2)-424 = 520 - 424 = 96
Ans : 300/124/96 assuming the first day its 300
Комментарии:
1. «предполагая, что в первый день его 300» — нет никаких предположений; Я утверждаю, что в 1-й день 300, а во 2-й 150. 300/124/96 следует квадратичному правилу; это означает бесконечную скорость рисования — кажется маловероятным.
2. @WillNess тогда какова скорость рисования, не упомянутая там, и предполагается, что, поскольку задается вопрос, дайте мне набор чисел, которые кажутся правильными, может быть много таких чисел без предоставления надлежащей информации
3. вопрос, заданный здесь, отличается от вопроса на связанной странице, он основан только на нем. вопрос здесь дает вам 2 числа и запрашивает третье.