Читая статью об устройстве на работу в ABBYY, встретил в ней упоминание задачи:
быстро – за O( log N ) арифметических операций над числами – найти N-е число Фибоначчи
Я задумался над ней и понял, что сходу в голову приходят только решения, работающие за время O(N). Однако позже решение было найдено.
Читать полностью »