Представим такую ситуацию. В правой руке я держу стопку экзаменационных работ. На каждой проставлен номер билета, от 1 до n. Порядок - случайный. В левой руке у меня пачка этих билетов, тоже n штук, но уже разложенных по порядку. Для проверки экзаменационной работы я достаю из правой пачки случайную работу и по порядку перелистываю билеты в левой пачке пока не найду нужный номер. На следующей итерации я опять должен перелистать билеты с этой позиции, пока не найду нужный, и так до конца. Вопрос: сколько в среднем перелистываний надо совершить для проверки всей пачки? Интерес чисто математический. Переход от перелистывания к например бинарному поиску уменьшит число перелистываний, но принципиально не изменит его зависимость от n.
Билеты из пачки не изымаются. Пример: в правой пачке работы идут в порядке 5-3-7. Тогда перелистывания левой пачки будут: 1->5->3->7, итого 4+2+4 = 10 перелистываний. N^2 явно не катит, потому что если работы будут лежать в порядке 1-2-3-..., то понадобится n-1 перелистываний - это явный минимум. А мне больше интересно среднее количество перелистываний для случайного порядка работ, ну и раскладка для максимально возможного их числа. Интуитивно видится что-то типа n-1-(n-1)-2-...
Тогда максимально возможное число перекладываний дано в моем ответе
это когда идет N 1 N-1 2 N-2 3 ...
Минимальное N-1
Среднее по ощущениям тоже квадратичная зависимость от N
т/е O(N*N) так как очень уж алгоритм напоминает пузырьковую сортировку - только сортировки как таковой нет
Решение:
Среднее колво перелистываний до первого билета равно (N-1)/2
Cреднее число перелистываний между двумя равномерно распределенными билетами на отрезке 1..N равно (N-1)/3,
всего после первого перелистывания отсается ровно (N-1) таких пар
Итого среднее число всего перелистываний:
(N-1)/2 + (N-1)*(N-1)/3
Что и является ответом.
Максимум дан в моем предыдущем ответе, он подходит и даже после уточнения условий.
Может не стоит писать просто так? А писать в чем конкретно не слогласен. Вот доказательство math.stackexchange.com/questions/195245/average-di...
Естественно для дискретного случая для 1..N (N-1)/3 это нижняя оценка среднего расстояния, которая при увеличении N стремится к точной оценке.
Задача решена верно!
Для малых N если они интересуют, формулу надо подправлять используя комбинаторику, например для N=2 среднее расстояние между парами не (N-1)/3 а точно известно и равно 1
тогда формула дает
(2-1)/2 + (2-1)*1 = 1.5 перелистываний для двух билетов
и это точный ответ.
Так как условие не полно, а именно не указано изымается ли билет из пачки, да и правила листания тоже нечеткие
то считаю что он остается - имею право :-), а листаю сверху
до каждого билета с номером k надо листать (k-1) раз - просуммировать от Сумма(k= 1 до N, (k-1)) = (N-1)*N/2
Простой