что означает среднее значение по сравнению с массивом с длиной х в быстрой сортировке

Question

в этой формуле и продолжить этот вопрос Я думаю, что если мы примем n равным 3, то у нас будет массив типа A = {4,5,7}

и с формулой, мы получаем 8 из n = 3, и это означает, что среднее сравнение для массива с длиной 3 равно 8, и это так странно!

1. что именно происходит в быстрой сортировке, чтобы получить среднюю форму сравнения 8массив такой короткий! и происходит, многие сравнивают, и это так плохо! верно?

Я думаю, что если мы сравним массив с 4 шагами, это будет быстрее, чем использование quickSort!

Answer 1

Итак, ваш вопрос, кажется, о формуле

E [X] = E [сумма (i, 1, n-1, сумма (j, i + 1, n, p _{i), j} ))]

в это изображение, которое вы загрузили в другом вопросе.

Здесь E [X] означает ожидаемое значение. Проще говоря: значение X будет в среднем получаться, если вы будете проводить эксперимент (сортировку случайного массива) много раз.

p _{i, j} - это вероятность того, что элемент i и элементj сравниваются друг с другом во время выполнения алгоритма. Для хорошего алгоритма случается, что элемент i сравнивается с элементом k, а элемент k с элементом j, что часто делает ненужным действительно сравнивать элемент i и элемент j. Следовательно, чем лучше алгоритм, тем ниже эта вероятность p _{i, j} .

В худшем случае, например, когда n равно только 3, вы можете иметь p _i,j = 1. Если затем вычислить формулу, вы получите ее для n = 3, E [X] = 3, поскольку для (i, j) есть только три комбинации: (1,2), (1,3) и (2,3). Это означает, что при n = 3 всегда выполняется 3 сравнения. Это одинаково для всех хороших алгоритмов, потому что вы не можете использовать item_i

. Для больших n есть много шансов воспользоваться тем, что нет необходимости явно проверять все item_i и все item_j. Подробный анализ, например, доступен в статье Академии Хана .