Блог

Допустим, у меня есть несортированный массив Unsorted_Arr= [2, 8, 1, 3, 6, 7, 5, 4].

Прямо перед самым последним проходом слияния у меня было бы два массива, Arr_Left = [1, 2, 3, 8] и арр_райт = [4, 5, 6, 7]. Чтобы объединить их, мне нужно было бы полностью перебрать все n элементов Arr_Right и перебрать n-1 элементов Arr_Left. В общей сложности я бы пересек n-1 элементов исходного Unsorted_Arr. Отбросьте -1, и у меня есть временная сложность O(n) для слияния.

Хотя я понимаю, почему рекурсивная часть сортировки слиянием является log n, поскольку наш код содержит часть кода, которая выполняется с O(n), не должен ли наихудший сценарий сортировки слиянием быть O(n)?

Но эти два массива сами по себе не обязательно уже отсортированы, поэтому вам придется разделить их, а затем снова объединить. И вам придется повторять это до тех пор, пока в каждом массиве не останется только один или ноль элементов (потому что массив из 1 или 0 элементов всегда сортируется), а затем повторно объединить их все.

И на каждом уровне это, по крайней мере 2*n , операции (для всех разделенных массивов на этом уровне), которые относятся O(n) к каждому уровню.

Итак, сколько уровней глубины вам пришлось бы пройти при разделении, прежде чем каждый массив будет иметь длину всего 1 или 0? Это Log(n) .

Объединение количества уровней, которые вы должны разделить, а затем повторно объединить все подсписки ( O(Log(n)) ), с количеством операций, которые необходимо выполнить на каждом уровне ( O(n) ), становится: O(Log(n)) * O(n) что сводится к O(n*Log(n)) .