Алгоритм решения CLRS нуждается в более подробном обсуждении
Докажите, что индикаторная случайная величина Xk и значение T(max(k - 1, n - k)) независимы.
Ответ
Вероятность того, что X_k равно 1, не меняется, когда мы знаем максимальное значение k-1 и nk. Другими словами, Pr{X_k =a| max(k-1, nk)=m} = Pr{X_k=a} для a=0,1 и m=k-1, nk, поэтому X_k и max(k-1, nk) независимы.
Теперь, насколько я понимаю, k-1 — это нижняя сторона подмассива, где каждый элемент массива <k, а nk — это верхняя сторона массива, где каждый элемент массива > k. Таким образом, мы можем рассматривать k как точку опоры. X_k является индикаторной случайной величиной, и X_k = 1, когда подмассив A[p..q] имеет ровно k элементов.
Теперь ответ сказал, что X_k=1, когда мы знаем max из k-1 и nk. Я считаю, что max из k-1 будет k-1-м элементом массива, а max из nk - n-м элементом массива. Какая связь между максимальным элементом и индикаторной случайной величиной 1?
Pr{X_k=a} при условии, что max(k-1, nk)
max(k-1, nk) означает, что максимальный элемент должен находиться на n-й позиции.
Кроме того, мне непонятно определение a и m .
Я нашел этот вопрос с ответом на вопрос 9.2-2 ссылки на решение CLRS.
Хотя ответ определен в ссылке, я считаю, что немного больше объяснений этого ответа было бы более полезным.