Сложность операции поиска элемента по индексу

1️⃣ Как кратко ответить

Сложность операции поиска элемента по индексу в массиве (array) составляет O(1), так как массивы обеспечивают прямой доступ к элементам по индексу. В списках Python (реализованных как динамические массивы) также O(1). В связных списках сложность O(n), так как требуется последовательный обход элементов.

2️⃣ Подробное объяснение темы

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

Массивы

Массивы — это структуры данных, которые хранят элементы в непрерывном блоке памяти. Каждый элемент массива имеет свой индекс, который указывает на его позицию в массиве. Благодаря этому, доступ к элементу по индексу осуществляется за постоянное время O(1).

Пример на Python

array = [10, 20, 30, 40, 50]
element = array[2]  # Получение элемента по индексу 2
print(element)  # Вывод: 30

• array = [10, 20, 30, 40, 50]: Создаем массив из пяти элементов.
• element = array[2]: Получаем элемент с индексом 2. Это операция O(1), так как доступ осуществляется напрямую.
• print(element): Выводим значение элемента, которое равно 30.

Связные списки

Связные списки — это структуры данных, где каждый элемент (узел) содержит данные и указатель на следующий элемент. В отличие от массивов, элементы связного списка не хранятся в непрерывной области памяти. Поэтому, чтобы получить элемент по индексу, необходимо последовательно пройти от начала списка до нужного элемента. Это делает сложность операции O(n), где n — количество элементов до нужного индекса.

Пример на Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
​
class LinkedList:
    def __init__(self):
        self.head = None
​
    def get(self, index):
        current = self.head
        count = 0
        while current:
            if count == index:
                return current.data
            current = current.next
            count += 1
        return None
​
# Создаем связный список
linked_list = LinkedList()
linked_list.head = Node(10)
second = Node(20)
third = Node(30)
linked_list.head.next = second
second.next = third
​
# Получаем элемент по индексу 2
element = linked_list.get(2)
print(element)  # Вывод: 30

• class Node: Определяем класс узла, который содержит данные и указатель на следующий узел.
• class LinkedList: Определяем класс связного списка с методом get для получения элемента по индексу.
• linked_list.head = Node(10): Создаем первый узел и назначаем его головой списка.
• second = Node(20), third = Node(30): Создаем второй и третий узлы.
• linked_list.head.next = second, second.next = third: Связываем узлы между собой.
• element = linked_list.get(2): Получаем элемент с индексом 2. Для этого требуется пройти по списку, что занимает O(n) времени.
• print(element): Выводим значение элемента, которое равно 30.