Привет народ,
Вам говорили, что временная сложность сортировки слиянием составляет nlogn, и если вы похожи на меня, вам интересно, почему.
В этой статье я помогу вам получить полное представление о сложности nlogn применительно к сортировке слиянием.
Простейшее представление о логарифме
Возможно, вы знаете из школы, что у логарифмов есть основание,
но в анализе временной сложности основание всегда равно 2.
Я не хочу пугать вас математическими понятиями,
на самом деле, я лучше покажу, что такое logn, на примере.
Вы можете представить logn как серию последовательных делений пополам.
Предположим, у нас есть сладкий торт,
который кто-то разрезал на 4 ломтика.
съешьте его половину,
съешьте половину оставшегося (не вторую половину! ),
оставь кусочек любимой мамочке!
Теперь посчитайте, сколько шагов вам понадобилось, чтобы получить один кусок.
Всего 2 шага, не так ли?
Хорошо, это число равно логарифму 4 кусочков торта.
А теперь представьте, что вместо торта массив, а вместо вас голодный компьютер…
Представили?
Хорошо, теперь пусть компьютер съест половину массива,
тогда половина оставшихся,
и так далее…
Когда остался только один элемент, посчитайте, сколько шагов он прошел.
Я думаю, вы поняли идею!
Это означает, что: логарифм говорит вам, сколько шагов занимает процесс последующего деления чего-либо пополам.
Первая часть головоломки: СЛИЯНИЕ
Сортировка слиянием названа так потому, что она работает путем слияния двух упорядоченных массивов (для этого используется метод двух указателей).
Посмотрим на этот псевдокод
Этот фрагмент кода занимает линейное время, фактически он будет выполнять столько операций, сколько элементов в самом длинном массиве.
Это первая часть головоломки:
первое n в nlogn.
Вторая часть головоломки: ПОЛОВИНА
Для тех немногих, кто еще здесь, я собираюсь показать, откуда берется logn в nlogn!
Давайте посмотрим эту гифку
Как вы видите, массив впоследствии делится пополам до отдельных элементов.
Сортировка слиянием представляет собой комбинацию
процесса деления пополам в GIF
и показанной ранее функции псевдокода.
Это работает, потому что когда есть только массивы с одним элементом (нижняя часть GIF), они гарантированно уже отсортированы!
Отсортируйте их слиянием попарно,
пройдите назад всю структуру,
пока не получите полный массив,
и все отсортировано!
Остаток: логарифм показывает, сколько шагов занимает процесс последующего деления чего-либо пополам.
Таким образом, в основном вы применяете эту функцию псевдокода, которая принимает n в качестве временной сложности, logn раз.
Бонус: сортировка слиянием (рекурсивная и итеративная)
Плавник
Надеюсь, вы нашли здесь полезную информацию.
Если это так, поставьте палец вверх и не забудьте подписаться!
