Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[52.54.111.228] |
|
Сообщ.
#1
,
|
|
|
Всем прива!
Собственно - сабж. Давайте на примере Timsort. Вот цитата из вики: Цитата Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: O(n*log(n)). Требуется O(n) дополнительной памяти. Разработан для использования в языке Python[14]. Собственно, вопрос: сабж! В данном случае имеем два алгоритма, которые "сочетаем": 1) Сортировка вставками - вычислительная сложность O(n²) 2) Сортировка слиянием - вычислительная сложность O(n*log(n)) Откуда - результирующий O(n*log(n))? |
Сообщ.
#2
,
|
|
|
Сортировка вставками используется на малых фрагментах, скажем, порядка 100 элементов. Для каждого из таких фрагментов она выполнится быстрее, чем более сложные сортировки, т.к. у неё меньше накладные расходы (множитель для выражения со сложностью, который обычно опускают).
Таким образом общее время немного уменьшается, сложность O(n*log(n)) сохраняется, потому что на вставки тратится в данном случае n/100 * 100^2 = 100*n - т.е. линейное время от общего количества элементов. |
Сообщ.
#3
,
|
|
|
Вообще-то алгоритм сортировки в Python ещё немного более сложен.
Для начала ищутся строго убывающие последовательности. Эти последовательности сортируются просто обратной перестановкой. Потом производится разбивка на возрастающие серии, составляется оптимальный порядок объединения. Первыми при этом объединяются короткие пары. Объединение производится методом слияния (слияние может производиться как слева направо, так и справа налево, в зависимости от того какая из сливаемых последовательность короче). В некоторых случаях быстрее произвести слияние методом вставок (когда одна из последовательностей имеет длину один или два элемента). Это для обычной, возрастающей сортировки. Добавлено Производится это параллельно по мере обнаружения описанных подцепочек |
Сообщ.
#4
,
|
|
|
Для начала надо с трактовкой определиться.
Либо это выбор одного из существующих алгоритмов, в зависимости от размера данных, как говорил MBo Либо это что-то объединенное, "закрученное", как пишет amk. Ну, а так, можно построить график зависимости от тестов. Визуально определить чем его описать. |