Время выполнения Mergesort BigO

Question

В учебнике Снейпа «Недружественные алгоритмы для волшебников» утверждается, что время слияния сортировка O (n ^ 4). Это утверждение верно?

Решение: Да. Это утверждение технически правильно, потому что O (n ^ 4) дает только верхний ограничено, сколько времени занимает алгоритм. Тем не менее, это неприятно бесполезный ответ, поскольку жесткая граница составляет Θ(n log n).

Я не совсем понимаю, о чем говорит решение. Как O (n ^ 4) может быть правильным?

Answer 1

Большая O-нотация - это верхняя граница наихудшего случая для времени выполнения алгоритма.

Поскольку O (n ^ 4) выше наихудшего случая времени слияния, это технически правильно, поскольку оно обеспечивает ограничение -то есть.Производительность слияния никогда не будет иметь производительность хуже, чем O (n ^ 4).

Однако это бесполезно, потому что лучшим выражением времени выполнения является O (n log n), что является «самой жесткой» границей для слияниясортировать

Answer 2

Big-O - это набор, который включает в себя все, что работает так же быстро, как (foo) или быстрее. Little-O - это набор вещей, которые работают строго быстрее, чем (foo). Хотя правильно сказать, что mergesort это O (n ^ 4), это не очень полезно, потому что это Theta (n log n). Утверждение, что mergesort равен o (n ^ 4), немного более полезно, потому что нотация о-о никогда не используется для обозначения времени выполнения с большой тэтой.

Еще больше усложняя ситуацию, big-O часто используется, когда более подходящим является big-theta, просто потому, что у большинства клавиатур нет theta.