Что такое O(1)?

Что такое O(1)

O(1) — это временная сложность (time complexity) в нотации Big O, которая означает, что операция выполняется за постоянное время, независимо от размера входных данных. Это самая оптимальная временная сложность в алгоритмах.

Основная идея

Время выполнения операции не зависит от размера задачи:

Число элементов:  1      10      100      1000      10000
Время выполнения: 1 нс   1 нс    1 нс     1 нс      1 нс

Сложность O(1) означает, что операция выполняется за примерно одно и то же время всегда.

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

1. Доступ к элементу массива по индексу

int[] arr = {10, 20, 30, 40, 50};
int element = arr[2];  // O(1) - прямой доступ к элементу
System.out.println(element);  // Output: 30

Компьютер может мгновенно вычислить адрес элемента в памяти, используя формулу:

адрес = адрес_массива + (индекс × размер_типа_данных)

2. Получение элемента из HashMap

Map<String, Integer> map = new HashMap<>();
map.put("John", 25);
map.put("Alice", 30);
map.put("Bob", 28);

int age = map.get("Alice");  // O(1) в среднем случае
System.out.println(age);  // Output: 30

HashMap использует хеширование для мгновенного поиска элемента.

3. Операции с переменной

int a = 5;
int b = 10;
int c = a + b;  // O(1) - просто арифметическая операция
System.out.println(c);  // Output: 15

4. Проверка элемента в HashSet

Set<String> cities = new HashSet<>();
cities.add("Moscow");
cities.add("Paris");
cities.add("Tokyo");

boolean exists = cities.contains("Paris");  // O(1)
System.out.println(exists);  // Output: true

5. Push/Pop операции в Stack

Stack<Integer> stack = new Stack<>();
stack.push(1);  // O(1) - добавление в конец
stack.push(2);
stack.push(3);

int top = stack.pop();  // O(1) - удаление с конца
System.out.println(top);  // Output: 3

Граф сложности O(1)

Время
  ↑
  │         _______ O(1) - горизонтальная линия
  │        │
  │        │
  │        │
  └─────────────────────> Размер данных (n)
  0   n=100  n=1000  n=10000

Время выполнения остаётся примерно одинаковым при увеличении n.

Сравнение сложностей

// O(1) - Доступ к элементу массива
int element = arr[5];

// O(log n) - Бинарный поиск
Arrays.binarySearch(sortedArr, 42);

// O(n) - Линейный поиск
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == 42) break;
}

// O(n²) - Вложенные циклы (сортировка пузырьком)
for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {
        // операция
    }
}

// O(2ⁿ) - Экспоненциальная (рекурсия Фибоначчи)
private int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

График времени выполнения:

Время
  ↑
  │                    O(2ⁿ)
  │              O(n²)
  │          O(n)
  │      O(log n)
  │      O(1)___
  │      │
  │      │
  │      │_______
  └─────────────────────> n

Когда O(1) достижима

✅ Достижимо O(1):

• Доступ по индексу в массиве
• Получение значения из HashMap/HashSet
• Простые арифметические операции
• Проверка условия
• Push/Pop в Stack или Queue

❌ Невозможно O(1):

• Поиск элемента в неотсортированном массиве (требует O(n))
• Сортировка массива (требует минимум O(n log n))
• Проверка паттерна в строке (требует O(n·m))

Практический пример: оптимизация с O(1)

Неоптимальный код O(n²):

public class FindDuplicate {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 2, 5};
        
        // O(n²) - проверяем каждый элемент против всех остальных
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    System.out.println("Duplicate: " + arr[i]);
                }
            }
        }
    }
}

Для n=1000000 это будет миллиард операций!

Оптимизированный код O(n):

public class FindDuplicate {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 2, 5};
        
        // O(n) - используем HashSet для O(1) проверки
        Set<Integer> seen = new HashSet<>();
        for (int num : arr) {
            if (seen.contains(num)) {  // O(1)
                System.out.println("Duplicate: " + num);
            }
            seen.add(num);  // O(1)
        }
    }
}

Для n=1000000 это будет миллион операций!

Важное примечание: амортизированная O(1)

Некоторые операции имеют амортизированную сложность O(1), что означает, что в среднем они выполняются за O(1), но иногда могут быть медленнее:

List<Integer> list = new ArrayList<>();  // Динамический массив
list.add(1);      // O(1)
list.add(2);      // O(1)
list.add(3);      // O(1)
list.add(4);      // O(1) обычно, но O(n) при переполнении буфера

Когда ArrayList переполняется, он создаёт новый массив большего размера и копирует все элементы (O(n)). Но это происходит редко, поэтому амортизированная сложность остаётся O(1).

HashMap vs TreeMap

// HashMap - O(1) в среднем случае
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("key", 1);      // O(1)
int value = hashMap.get("key");  // O(1)

// TreeMap - O(log n) (использует красно-чёрное дерево)
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("key", 1);      // O(log n)
int value = treeMap.get("key");  // O(log n)

Лучшие практики

1. Используй HashMap/HashSet вместо ArrayList для поиска:

// Плохо - O(n)
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
if (list.contains("b")) {}  // O(n)

// Хорошо - O(1)
Set<String> set = new HashSet<>(Arrays.asList("a", "b", "c"));
if (set.contains("b")) {}  // O(1)

2. Избегай вложенных циклов:

// Плохо - O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // операция
    }
}

// Хорошо - O(n)
for (int i = 0; i < n; i++) {
    operation(i);  // O(1)
}

3. Используй индексацию вместо поиска:

// Плохо - O(n)
int element = list.stream()
    .filter(x -> x.getId() == 5)
    .findFirst()
    .orElse(null);

// Хорошо - O(1)
int element = map.get(5);  // Если использовать Map<Integer, Item>

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