Какова сложность доступа к элементу в различных структурах данных?

Сложность доступа к элементу зависит от типа и реализации структуры данных.

Основные структуры данных и их сложность доступа:

• Массив (Array):

  • Сложность: O(1)
  • Доступ осуществляется по индексу, зная начальный адрес и размер элемента.

• Связанный список (Linked List):

  • Сложность: O(n) в худшем случае (для односвязного), O(n) в лучшем (если элемент — первый)
  • Требуется последовательный обход от начала списка до нужного элемента.

• Дерево (Tree):

  • Бинарное дерево поиска (Binary Search Tree):
    • Сложность: O(log n) в среднем, O(n) в худшем случае (вырожденное дерево)
    • Эффективно для поиска, вставки и удаления.
  • Сбалансированное дерево (например, AVL, Red-Black Tree):
    • Сложность: O(log n)
    • Поддерживает логарифмическую сложность операций за счет балансировки.

• Хеш-таблица (Hash Table):

  • Сложность: O(1) в среднем, O(n) в худшем случае (при коллизиях)
  • Доступ осуществляется по хешу ключа, который указывает на место хранения данных.

Пример для массива:

// Доступ к элементу массива по индексу
int arr[] = {1, 2, 3, 4, 5};
int element = arr[2]; // O(1)

Пример для односвязного списка:

// Поиск элемента в односвязном списке
struct Node {
    int data;
    Node* next;
};

Node* head = ...; // Начало списка
int target_data = 3;
Node* current = head;
while (current != nullptr) {
    if (current->data == target_data) {
        // Элемент найден
        break; // Сложность O(n) в худшем случае
    }
    current = current->next;
}