Какова сложность времени для отсортированного массива, отсортированного связанного списка и дерева двоичного поиска в лучшем случае для вставки, удаления

Question

Какова сложность времени для отсортированного массива, отсортированного связанного списка и дерева двоичного поиска в лучшем случае для вставки, удаления (и почему?). Кроме того, как люди обычно определяют лучший случай из алгоритма. Я понимаю, как определить худший случай из алгоритма, например, для l oop будет O (n). До сих пор я обнаружил только средние и худшие случаи в Интернете, но ни один из них не показывает лучший случай.

Answer 1

Это зависит от того, что вы считаете лучшим случаем. Например, если я рассматриваю лучший случай как «вставить уникальный элемент / удалить уникальный элемент», вся древовидная структура занимает O (1) времени. В этом случае я думаю, что это не лучшие случаи, потому что

1. В Sorted Array a Linked List вы должны найти позицию, где вставьте новый элемент O (n), затем вы должны сдвинуть другие элементы (O (n) в массиве, O (1) в связанных списках), та же сложность для удаления
2. В деревьях двоичного поиска операции вставки / удаления занимают все время O (h), где h - высота дерева , Если ваше дерево сбалансировано (AVL или красно-черные деревья), h = O (log n), поэтому сложность становится O (log n)

В этом случае нотация big-O описывает все кейсы.

PS В общем, лучшие случаи не рассматриваются так много, потому что они уже рассматриваются в среднем кейсе.