Вы правы, что это немного сбивает с толку и не очень точно авторов. Лучше использовать повторения, подобные этому, для подсчета отдельных событий, таких как сравнения. Но тогда вы должны заложить детали конкретной реализации, и это становится неудобно. Это доказательство является своего рода оценкой, которая достаточно хороша, поскольку мы только ищем большое поведение Omega. Постоянные факторы не имеют значения.
Для того, чтобы понять это, думать о cn (который c раз n) как количество времени, которое требуется, чтобы сделать шаг слияния в списках с общей длиной n. Таким образом, c является грубым выражением для постоянного времени, которое требуется для обработки одного элемента: времени, которое требуется для выполнения одной итерации любого цикла, выполняющего слияние.
Вместо слияния он называет это «комбинацией». Он также предлагает, что для разделения списков для рекурсивной сортировки может существовать стоимость каждого элемента. В обычной реализации массива таких затрат на один элемент нет. У объединенного списка mergesort будет один, хотя: цикл, который делит большой список на две половины. Затем c представляет одну итерацию обеих петель.
Рекурсивный термин 2T(n/2) - это выражение для количества времени, которое требуется для сортировки двух подписок.
Вы могли бы сделать это выражение немного более точным, говоря
T(n) = 2T(n/2) + cn + k
где k постоянное время коды, который работает за пределами слияния (и раскол, если есть один) цикл: вызов функции над головой, Подсписок длина математики и т. д. Вы можете попытаться решить повторение с этим дополнительным термином как упражнение, чтобы доказать себе, что большой результат Омеги не меняется.
Может быть 'c * n' возможно? –
Это C * n, линейное время, константа действительно не имеет значения – amit
Но что он имеет в виду по времени для элемента массива разделения и сочетания шагов? – Sarthak