среда, 15 апреля 2015 г.

Two quotes…

Original in Russian: http://programmingmindstream.blogspot.ru/2015/04/blog-post_15.html

"In terms of mathematics, there’s no better way to check than to calculate. So, Shlemiel the painter’s algorithm.

Shlemiel the painter contracted to paint the dotted road center lines. On the first day, he was given a paint can, put it on the road and, by the end of the day, painted 300 m of center line. “Well done!”, the foreman said, "you work hand over hand!”, and paid him a penny.

The following day, Shlemiel painted 150 m. “Hrmph, this is not that great as yesterday but good enough”, the foreman said and paid him a penny.

The following day, Shlemiel painted 30 m. “30 meters, just that!", the foreman roared. “This is no good at all! You did 10 times more on the first day! What’s the matter?"

"Can’t hale it," Shlemiel said. "Every day I go away from the can farther and farther!"

Suppose, the number of meters painted within one approach to the can is constant and equals Dp, so on the first day the painter covered the distance:

Dp + Dp + 2Dp + 2Dp + 3Dp + 3Dp +... + M*Dp + M*Dp = [где M*Dp = 300] = 2Dp (1+2+3+... +M) .

It is more clear with Dp taken as 1 m, in order to get rid of lengthy formulas. In this case, calculations are as follows:
2(1+2+3+...+300) – the first day,

the second day:
(301 + 301 + 302 + 302 + ... + (N-1) + (N-1) + N + N = 2 (301 + 302 + (N-1) + N) = [ since natural series sum 1+2 + 3+ N = N(N+1)/2 – is the so-called triangular number ] = 2* (N(N+1)/2 - 150*301) = N^2 + N - 90300 , А это O(N^2).

This is so if we assume the line painting quickness and the speed of movement to be constant. At the same time, if we start from the distance painted, the time is also O(N^2). By the way, the figures given by Joel Spolsky about it are rather exaggerated not to painter’s credit. To see it, one needs only to solve an equation. That is so somehow..."

"I’ll say... I am jealous of the people who know what “natural series sum” is and who can find algorithm complexity... Seems to me, I am too old to learn it."

I personally belong to the second group of people...

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

Отправить комментарий