Что такое O в оценке алгоритмической сложности

Ответ

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

Примеры:

O(1) — константная сложность (доступ к элементу массива по индексу).
```
const arr = [1, 2, 3];
console.log(arr[0]); // O(1)
```
O(n) — линейная сложность (перебор массива).
```
for (let i = 0; i < arr.length; i++) { // O(n)
  console.log(arr[i]);
}
```

O(n²) — квадратичная сложность (вложенные циклы).

for (let i = 0; i < n; i++) {       // O(n²)
  for (let j = 0; j < n; j++) {
    console.log(i, j);
  }
}

Важно учитывать доминирующий член (например, в O(n + n²) → O(n²)).