O (N регистрируют N), Сложность - Подобный линейному?
Сортировать кортежи, затем перечислить, если t1.right> = t2.left => объединить и перезапустить с новым списком, ...
->
def f(l, sort = True):
if sort:
sl = sorted(tuple(sorted(i)) for i in l)
else:
sl = l
if len(sl) > 1:
if sl[0][1] >= sl[1][0]:
sl[0] = (sl[0][0], sl[1][1])
del sl[1]
if len(sl) < len(l):
return f(sl, False)
return sl
6 ответов
Увеличьте график, и вы увидите, что O (n logn) не совсем прямая линия. Но да, это довольно близко к линейному поведению. Чтобы понять, почему, просто возьмите логарифм нескольких очень больших чисел.
Например (основание 10):
log(1000000) = 6
log(1000000000) = 9
…
Итак, чтобы отсортировать 1000000 чисел, сортировка O (n logn) добавляет жалкий множитель 6 (или просто немного больше, поскольку большинство алгоритмов сортировки будут зависеть от логарифмов с основанием 2). Не так уж и много.
Фактически, этот логарифмический коэффициент настолько чрезвычайно мал, что для большинства порядков установленные алгоритмы O (n logn) превосходят алгоритмы линейного времени. Ярким примером является создание структуры данных массива суффиксов.
Недавно меня укусил простой случай , когда я попытался улучшить быструю сортировку коротких строк с помощью сортировки по основанию . Оказывается,
Для еще большего удовольствия в том же ключе попробуйте построить график времени, затраченного на n операций на стандартном структура данных непересекающегося набора . Было показано, что оно асимптотически n α ( n ), где α ( n ) является обратной функцией функции Аккермана (хотя ваш обычный учебник по алгоритмам, вероятно, покажет только границу n log log n или, возможно, n log * n ]). Для любого числа, которое вы, вероятно, встретите в качестве входного размера, α ( n ) ≤ 5 (и действительно log * n ≤ 5), хотя оно приближается к бесконечности асимптотически.
Я полагаю, вы можете извлечь из этого урок, что, хотя асимптотическая сложность - очень полезный инструмент для размышлений об алгоритмах, это не совсем то же самое, что практическая эффективность.
- Обычно алгоритмы O (n * log (n)) имеют логарифмическую реализацию с двумя основаниями.
- Для n = 1024, log (1024) = 10, поэтому n * log ( n) = 1024 * 10 = 10240 вычислений, увеличение на порядок.
Итак, O (n * log (n)) похоже на linear только для небольшого количества данных.
Совет: don Не забывайте, что быстрая сортировка очень хорошо работает со случайными данными и что это не алгоритм O (n * log (n)).
log (N) - это (очень) примерно количество цифр в N. Таким образом, по большей части разница между log (n) и log (n + 1)
Попробуйте провести поверх нее реальную линейную линию, и вы увидите небольшое увеличение. Обратите внимание, что значение Y на уровне 50,0000 меньше, чем значение 1/2 Y на уровне 100000.
Оно есть, но оно небольшое. Вот почему O (nlog (n)) так хорош!
К вашему сведению, быстрая сортировка на самом деле O (n ^ 2), но со средним случаем O (nlogn)
FYI, есть довольно большая разница между O (n) и O (нлогн). Вот почему он не ограничивается O (n) для какой-либо константы.
Для графической демонстрации см:
