Как все знают, что обработка сортировки, которая оптимизируется, занимает меньше времени, чем обычная сортировка? Узнав, что оптимизация рода занимает меньше времени, сначала подумал, что приходит мне на ум: «Что делает быстрее»?Почему обработка «оптимизировать сортировку» занимает меньше времени, чем обычная сортировка?
Основная причина, по которой оптимизированная сортировка выполняется быстрее, заключается в том, что она уменьшает количество сравнений и/или перемещений двух элементов.
Если вы думаете о наивных наихудших типах N элементов, где вы сравниваете каждый из N элементов с каждым из других элементов N-1, то существует общее количество N * (N-1) = N^2-N сравнения. Одним из возможных способов оптимизации процесса было бы сортировать меньший список - например, N/2. Это потребует сравнений N/2 * (N/2-1) или N^2/4-N/2. Но, конечно, вам нужно будет сделать это на обеих половинах списка, что бы удвоить это - так что N^2/2-N сравнения. Вам также понадобится N/2 дополнительных сравнений, чтобы объединить две половинки обратно вместе, поэтому общее количество сравнений для сортировки двух полуразмерных списков и их слияния будет равно N^2/2-N + N/2 или N^2/2-N/2 - половина количества сравнений для сортировки всего списка. Рекурсивно подразделяя ваши списки на 2 элемента, которые могут быть отсортированы только с одним сравнением, может обеспечить значительную экономию в количестве сравнений. Существуют и другие идеи «разделяй и властвуй», а также способы использовать обнаруженные симметрии в списках, чтобы помочь оптимизировать алгоритм сортировки и в сочетании с различными способами упорядочивания данных в памяти (массивы против связанных списков против кучек против деревьев ... и т. д.), это приводит к различным оптимизированным алгоритмам.
+1 спасибо за ваш ответ –
По определению «оптимизировано», я думаю .. Не совсем понятно, что вы здесь задаете. – Blorgbeard