Структура данных - Большая O доступа и индексации. Что они на самом деле означают?

Question

Я нашел две статьи в Интернете:

First

Second

Что меня смущает это термины Индексация и доступа они используют. Они имеют в виду одно и то же?

Возьмите массив как пример:

Первый говорит Big O доступа является O (1). Второй говорит, что Big O индексации - O (1). Поэтому я предполагаю, что оба они говорят, указав индекс x, вы можете получить значение array[x] в O (1).

Возьмите Hash Table в качестве примера:

Первый говорит Big O доступа является N/A. Я думаю, что это связано с тем, что с помощью Hash Table вы делаете только с помощью ключа. Вы не получаете значение по индексу. Но второе говорит, что Big O индексации - O (1). Может быть, это относится к на этот раз?

Теперь возьмите бинарное дерево как пример:

Первый: Доступ O (LogN). Второе: индексирование - O (logN).

Что?

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

Пожалуйста, помогите мне получить разъяснения. Благодаря!

Answer 1

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

Более конкретно:

• в массивах, индексации или Access, конечно, O (1), когда речь идет о доступа, например, 3-го элемента, а поиск по О (п) в связи с линейной проход требуется худший случай.
• В Hashtables хорошо указано, что мы не можем ссылаться на индексирование, например , что является третьим элементом - этот вопрос не имеет смысла. В первой статье указано N/A с учетом вышеуказанного уведомления. Вторая статья считает, что индексирование Hashtable - это поиск элемента (где вы знаете хэш-ключ элемента). Тогда это правда, что нахождение элемента, если у вас хорошая хэш-таблица (хорошая длина и самая важная хорошая хэш-функция), это почти удобное время O (1).
• В двоичных деревьях поиск - поиск элемента O (logn). Здесь первая статья с использованием слова «доступ» относится к поиску элемента, как вы хорошо указали это.Вы не можете получить значение из двоичного дерева по индексу, но второе изделие путем индексации означает поиск, поскольку индексирование в другом случае не означает ничего. Обратите внимание, что поиск (или доступ или индексирование или поиск ) в двоичных деревьях поиска не O (logn), а O (n), потому что представляет случай, когда мы вставляем отсортированные элементы в дерево (например, 1,2,3,4 , 5, ...), то дерево становится списком и поиск является линейным. Много раз упоминается, что это O (logn), потому что случай, когда элементы отсортированы, изменяется редко и в большинстве случаев требуется O (logn) (но это асимптотическая сложность среднего случая, а не хуже!) , Вы получите O (logn), если вы используете деревья AVL, где дерево всегда сбалансировано, а поиск - O (logn).

Так что в Hashtables и деревьях двоичного поиска в приведенных выше статьях индексирование доступа называется поиском.