Вставка вроде сложности O (n ^ 2) и использование бинарного поиска по предыдущим значениям для улучшения сложности

Question

Как изменится сложность алгоритма (с сортировкой вставки O(n^2)), если вы изменили алгоритм для использования двоичного поиска вместо поиска по предыдущим значениям, пока не найдете место для вставки текущего значения.Кроме того, когда это будет полезно?

Answer 1

Ваша новая сложность все еще квадратична , так как вам нужно переместить все отсортированные части вправо.Следовательно, использование бинарного поиска только незначительно лучше.

Я бы рекомендовал алгоритм быстрой сортировки (за O(n log n) время) для больших массивов, алгоритм сортировки с квадратичной вставкой подходит только для небольших массивов.