17 июн. 2012 г.

Принцип Дирихле

Кажется, это было ещё в седьмом классе, когда упоминался принцип Дирихле:

Если есть M предметов, которые надо разложить по N ящиков, причём M > N, тогда хотя бы в одном ящике будет более одного предмета.

К этому прилагалась задача типа: население Москвы 10 млн человек, среднее кол-во волос у человека 1.5млн, у скольких людей в мск одинаковое кол-во волос.

Сейчас я работаю в очень высоком здании, в котором много этажей и компаний - например, едет в лифте 6 человек и лифт будет останавливаться на 3 этажах. Казалось бы всё очевидно - где-то выйдет более, чем один человек.

Можно ли сказать что-то больше ? Например, что на каждом этаже выйдет по 2 человека ?

Используя метод пристального взгляда часто можно определить, что незнакомые люди работают в одной компании - как правило это либо, соблюдение ими дресс кода, либо просто то, что они друг с другом общаются.

т.о. зная что-то о специфике данных можно дать более точный и лучший ответ.

Один из наглядных примеров - упаковка доменных объектов в пачки (batches).

Так записывая каждый объект в поток напрямую мы получаем объём данных
V ~ O(N),
в то время как зная о специфике данных, о том, что это пачка, можно достигать
V >> O(N).