Еще о мышлении...
Jan. 30th, 2018 10:39 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
a_jellyНедавно мне попалась задачка по программированию: есть множество точек на плоскости, заданных своими координатами (пусть целыми). Нужно найти максимальное количество точек, лежащих на одной прямой.
Задача не то чтоб очень трудная. Если подумать, то относительно быстро можно найти решение работающее за O(N^2), где N - число точек. Тем не менее, моё чуйство прекрасного его не принимает. Т.е. умом я понимаю, что возможно быстрее никак не получится, но душой принять не могу.
А ведь бывают задачи, где перебор аж O(N^3). Я уж молчу об NP-сложных проблемах.
Но суть-то не в этом. Речь о критериях. Я думаю, человек настолько "программист в душе" насколько быстро его начинает анноить большой перебор. Конкретно для меня эта граница пролегает где-то между n*log(n) и n^2. Не скажу точнее...
Задача не то чтоб очень трудная. Если подумать, то относительно быстро можно найти решение работающее за O(N^2), где N - число точек. Тем не менее, моё чуйство прекрасного его не принимает. Т.е. умом я понимаю, что возможно быстрее никак не получится, но душой принять не могу.
А ведь бывают задачи, где перебор аж O(N^3). Я уж молчу об NP-сложных проблемах.
Но суть-то не в этом. Речь о критериях. Я думаю, человек настолько "программист в душе" насколько быстро его начинает анноить большой перебор. Конкретно для меня эта граница пролегает где-то между n*log(n) и n^2. Не скажу точнее...