Вероятность сомнений

Question

Im работает над проблемой, которая идет как - Существует изначально неупорядоченный набор чисел. и цель состоит в ее сортировке. сортировка должна выполняться путем перетасовки чисел, пока они не попадут в их правильные места (да, Bogosort'ish :)). Перетасовка имеет одну оптимизацию, которая, если после перетасовки любые элементы к началу или к концу списка попадают в их правильные места, эти элементы будут фиксированы, а остальные элементы будут перетасованы с использованием вышеуказанной логики. Задача состоит в том, чтобы вычислить среднее количество повторов, необходимых для сортировки первоначально неупорядоченного набора чисел, скажем 6. Я знаю его последовательность распределения вдоль линии вероятности, но не могу полностью полностью обнулить ее. Будем очень благодарны за любые предложения/рекомендации в правильном направлении или подходе.

Thanks

Answer 1

Это может быть рассчитано рекурсивно.

• Список длины 0 требует в среднем 0 перетасовки. f (0) = 0.
• Список длины 1 требует в среднем 0 перетасовки. е (1) = 0.
• список длиной 2 после перетасовки имеет несколько возможностей:
  • Это уже отсортирован (50% шанс): 0 перемешивает.
  • Он еще не отсортирован (50% шанс):
    • Перемешивание сортирует его: 1 shuffle.
    • Перемешать не помогает, нам нужно попробовать еще раз: 1 + f (2) перетасовки.

Это CNA быть записан как:

f(2) = ((1/2) * 0) + ((1/2) * (1/2) * 1) + ((1/2) * (1/2) * (1 + f(2)). 
f(2) = 2/3 

Вы можете продолжать таким образом, чтобы большие входы, уменьшая их меньшие ресурсы, которые вы уже решены.