Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Яка часова складність доступу за індексом?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

## Коротка відповідь

Доступ за індексом у звичайному та динамічному масиві (Array, std::vector, ArrayList, Python list, JS Array) - O(1). У зв'язних списках - O(n). У деревах/rope/персистентних векторах - O(log n) (часто O(logₖ n)).

## Детальне пояснення

Під «доступом за індексом» розуміють операцію отримати елемент за позицією i. Складність залежить від внутрішньої будови структури даних.

### Чому масиви дають O(1)

- Неперервна пам'ять: елемент i лежить за адресою base + i * size, обчислюється за константний час.
- Складність не залежить від n (кількості елементів), лише від i та розміру елемента.
- Перевірка меж, кеш-влучання, page fault - це константні фактори, вони не змінюють асимптотику.

### Приклади коду

```cpp
// C++: статичний масив і std::vector, індексування O(1)
#include <vector>
#include <iostream>
int main(){
    int a[5] = {10,20,30,40,50};
    std::vector<int> v = {10,20,30,40,50};
    std::cout << a[3] << " " << v[3] << "\n"; // 4-й елемент, O(1)
}
```

```python
# Python: list, динамічний масив, доступ за індексом O(1)
arr = [10, 20, 30, 40, 50]
print(arr[3])  # 40
```

```javascript
// JavaScript: Array, середній випадок O(1) для щільних масивів
const arr = [10, 20, 30, 40, 50];
console.log(arr[3]); // 40
```

```java
// Java: Array і ArrayList, доступ за індексом O(1)
import java.util.*;
class Main{
  public static void main(String[] args){
    int[] a = {10,20,30,40,50};
    System.out.println(a[3]); // 40
    List<Integer> list = new ArrayList<>(Arrays.asList(10,20,30,40,50));
    System.out.println(list.get(3)); // 40
  }
}
```

### Коли доступ за індексом не O(1)

| Структура | Складність | Коментар |
|---|---|---|
| Однозв'язний/двозв'язний список | O(n) | Потрібно пройти i вузлів від голови/хвоста. |
| Дерева (B-дерево, сегментне, Fenwick за індексом) | O(log n) | Перехід по рівнях дерева. |
| Rope/мотузковий рядок | O(log n) | Рядок - дерево шматків; пошук за індексом іде по дереву. |
| Персистентний вектор (напр. Clojure) | O(logₖ n), зазвичай O(log₃₂ n) | Дерево з високою розгалуженістю дає майже константну глибину. |
| Deque/LinkedList (Java) за індексом | O(n) | Немає прямого випадкового доступу. |
| JS розріджені масиви | Амортизовано O(1), висока константа | Можуть зберігатися як хеш-таблиця/елементи властивостей, без щільного буфера. |

- Рядки: доступ до i-го байта/код-юніта - зазвичай O(1). Але доступ до i-го графемного кластера (видимого «символу» Unicode) може вимагати проходу, аж до O(n).
- Асоціативні масиви/словники не індексуються за позицією - там доступ за ключем, зазвичай амортизовано O(1), а не за індексом.

### Амортизованість проти найгіршого випадку

Динамічні масиви іноді перевиділяють пам'ять при рості; це впливає на операції вставки/розширення, але не на читання за індексом: get(i) лишається O(1) у найгіршому випадку. Вставки/видалення в середині - O(n), але це інша операція.

### Підсумок

Якщо структура - неперервний масив (зокрема динамічний), доступ за індексом - O(1). Щойно дані розбиваються на вузли або рівні (списки, дерева, rope, персистентні структури), складність зростає до O(n) або O(log n).

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати456 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.