Какая оценка времени доступа по индексу к элементу массива?

Какая оценка времени доступа по индексу к элементу массива?

Ответ: O(1) — constant time (констатное время)

Доступ к элементу массива по индексу — это одна из самых быстрых операций в программировании. Независимо от размера массива (100 элементов или 1 миллион), время доступа всегда одинаковое.

Почему O(1)?

Как работает память и индексирование

// Массив в памяти хранится как блок последовательных ячеек
const arr = [10, 20, 30, 40, 50];

// В памяти это выглядит так (по адресам):
// Адрес: 0x1000  0x1004  0x1008  0x1012  0x1016
// Значе: [10]    [20]    [30]    [40]    [50]
// Индекс: 0      1       2       3       4

// Доступ по индексу: O(1)
arr[0]; // Прямой доступ на адрес 0x1000 - одна операция
arr[2]; // Прямой доступ на адрес 0x1008 - одна операция
arr[4]; // Прямой доступ на адрес 0x1016 - одна операция

Формула расчета адреса

Адрес элемента = Базовый адрес + (Индекс × Размер элемента)

Это простое математическое вычисление, которое выполняется за одну операцию, независимо от размера массива.

const arr = new Array(1000000); // 1 миллион элементов

// Все эти операции занимают одинаковое время (O(1))
arr[0];        // 1 операция
arr[500];      // 1 операция
arr[999999];   // 1 операция

Сравнение с другими операциями

Операции с массивами и их сложность

Практические примеры

Примеры O(1) операций

const arr = [1, 2, 3, 4, 5];

// Все эти операции: O(1)
arr[0];                    // Доступ
arr[100] = 101;            // Присвоение по индексу
arr.length;                // Получить длину
arr[arr.length - 1];       // Доступ к последнему элементу
const el = arr.pop();      // Удалить последний элемент
arr.push(6);               // Добавить в конец (обычно O(1) amortized)

Примеры O(n) операций

const arr = [1, 2, 3, 4, 5, ..., 1000000]; // 1 миллион элементов

// Все эти операции: O(n) - зависит от размера
arr.indexOf(999999);       // Нужно проверить до 1 млн элементов
arr.includes(500000);      // Нужно проверить элементы
arr.filter(x => x > 3);    // Проверяет каждый элемент
arr.map(x => x * 2);       // Обрабатывает каждый элемент
arr.forEach(x => {...});   // Итерирует все элементы
arr.find(x => x === 500000); // Потенциально O(n)

Big O нотация

Таблица сложности (от лучшей к худшей)

O(1)      - Константное время (лучшее)
O(log n)  - Логарифмическое (очень хорошо)
O(n)      - Линейное (приемлемо)
O(n log n) - Логлинейное (нормально)
O(n²)     - Квадратичное (медленно)
O(n³)     - Кубическое (очень медленно)
O(2ⁿ)     - Экспоненциальное (ужасно)
O(n!)     - Факториальное (катастрофа)

Визуализация

Время выполнения
       |
     n |  n!
O(n!) | /
       |/
       |
 O(2ⁿ)|    2ⁿ
       |   /
   n² | /
O(n²)| /
       |/___________
   n  |/  n
 O(n) |____________
       |
 log n |__________ log n
O(log n)|     /
        |    /
     1  |___________
 O(1)   |
        |_____________________ n (размер)

Практическое значение

Скорость разных операций с массивом из 1 млн элементов

const arr = new Array(1000000).fill(0).map((_, i) => i);

// O(1) операции
console.time('access');
for (let i = 0; i < 1000000; i++) {
  arr[i]; // Очень быстро: ~1ms
}
console.timeEnd('access');

// O(n) операции
console.time('search');
arr.indexOf(999999); // Медленно: ~10ms (нужно проверить все элементы)
console.timeEnd('search');

// O(n log n) операция
console.time('sort');
arr.sort((a, b) => b - a); // Очень медленно: ~100ms
console.timeEnd('sort');

Амортизированная сложность

Для некоторых операций нужно учитывать амортизированную сложность:

// push() обычно O(1), но иногда O(n)
const arr = [1, 2, 3];
// Массив имеет capacity = 4
arr.push(4); // O(1) - есть свободное место

// Теперь capacity исчерпан
arr.push(5); // O(n) - нужно расширить массив и скопировать все элементы

// Результат: O(1) amortized - в среднем это O(1)

Индексирование в других структурах данных

// Массив - O(1) доступ по индексу
const arr = [1, 2, 3, 4, 5];
arr[2]; // O(1)

// Связный список - O(n) доступ по позиции
class LinkedListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

const head = new LinkedListNode(1);
head.next = new LinkedListNode(2);
head.next.next = new LinkedListNode(3);

// Доступ к 3му элементу: нужно пройтись с начала
// head -> next -> next (O(n))

// Объект (хеш-таблица) - O(1) средняя сложность
const obj = { a: 1, b: 2, c: 3 };
obj['b']; // O(1) в среднем

Итоги

Доступ к элементу массива по индексу = O(1)

Потому что:

1. Массив хранит элементы в последовательных ячейках памяти
2. Адрес вычисляется математически: базовый адрес + (индекс × размер)
3. Это вычисление занимает одну операцию, независимо от размера массива
4. Размер массива (100 или 1 миллион элементов) не влияет на время доступа

Это фундаментальное преимущество массивов перед другими структурами данных (связные списки, хеш-таблицы) и причина, по которой индексный доступ так широко используется в программировании.