Потешная алгоритмическая задача
Два года назад я выборочно читал книгу «Грокаем алгоритмы». Тогда я подумал, что понятие алгоритмической сложности оперирует достаточно ограниченным набором O(.): O(1), O(n), O(lg2n), O(n^2), ...
Но есть же и другие математические операции!
Мои ответы следующие: У человека значительная часть головы отвечает за восприятие визуальных образов. Отсутствие таковых из коробки в программировании сильно сокращает наши мощности. twitter.com/itunderhood/st…
Недавно я тут вещал на тему сложностей в программировании из-за отсутствия визуализации. Мне кажется, что алгоритмическая сложность также пала жертвой этого вопроса. Что такое алгоритмическая сложность? Это мерило необходимой работы.
twitter.com/itunderhood/st…
Если вам нужно перетащить 5 больших коробок из одного места в другое, и за раз вы можете перетащить только одну, то сколько походов нужно осуществить? Пять. А если коробок n, то походов в этом упрощённом примере нужно n. Значит, алгоритмическая сложность таскания коробок — O(n).
Итак, задачка. У нас есть квадратный лист бумаги, и мы его расчерчиванием на равные квадраты. Расчерчиваем, проводя прямые линии. Ничего не нарисовали, получили 1 большой квадрат. Нарисовали две линии — получили 4, нарисовали четыре линии — получили 9. Работа — рисование линий.
Какова алгоритмическая сложность расчерчивания листа на n квадратов? Тут стоит отметить, что n в этой задаче не может быть любым целым числом, может быть только квадратом: 1, 4, 9, 16, 25, и так далее.
По мере поступления решений, я буду усложнять задачу.
Герман Тебиев