Что такое О большое (Big O notation)?

Big O Notation: Анализ сложности алгоритмов

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

Что описывает Big O

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

• Big O показывает, как растёт время выполнения при увеличении размера входных данных (n)
• Фокусируется на наихудшем сценарии
• Игнорирует константы и младшие члены

Пример:

// O(n) — линейная сложность
int sumArray(List<int> arr) {
  int sum = 0;
  for (int i = 0; i < arr.length; i++) {
    sum += arr[i]; // Выполняется n раз
  }
  return sum;
}

// O(n²) — квадратичная сложность
int bubbleSort(List<int> arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Обмен элементов
      }
    }
  }
}

Основные классы сложности

1. O(1) — Константная сложность:

// Быстрее всего! Время не зависит от размера данных
int getFirst(List<int> arr) {
  return arr[0]; // Один доступ по индексу
}

int getFromMap(Map<String, int> map, String key) {
  return map[key] ?? 0; // Хеш-таблица
}

2. O(log n) — Логарифмическая сложность:

// Двоичный поиск в отсортированном массиве
int binarySearch(List<int> arr, int target) {
  int left = 0, right = arr.length - 1;
  while (left <= right) {
    int mid = (left + right) ~/ 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) {
      left = mid + 1; // Исключаем половину
    } else {
      right = mid - 1;
    }
  }
  return -1;
}
// Для массива из 1,000,000 элементов: ~20 итераций

3. O(n) — Линейная сложность:

// Простой поиск
bool contains(List<int> arr, int target) {
  for (int num in arr) {
    if (num == target) return true; // Может быть n итераций
  }
  return false;
}

// Фильтрация списка
List<int> filterEven(List<int> arr) {
  return arr.where((num) => num % 2 == 0).toList();
}

4. O(n log n) — Квазилинейная сложность:

// Эффективная сортировка (quicksort, mergesort)
List<int> quickSort(List<int> arr) {
  if (arr.length <= 1) return arr;
  
  int pivot = arr[arr.length ~/ 2];
  List<int> less = arr.where((x) => x < pivot).toList();
  List<int> equal = arr.where((x) => x == pivot).toList();
  List<int> greater = arr.where((x) => x > pivot).toList();
  
  return [...quickSort(less), ...equal, ...quickSort(greater)];
}

5. O(n²) — Квадратичная сложность:

// Неэффективная сортировка (bubble sort)
void bubbleSort(List<int> arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

// Вложенные циклы
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    // Выполняется n * n раз
  }
}

6. O(2^n) — Экспоненциальная сложность:

// Наивное решение проблемы коммивояжёра
int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // Ужасно медленно!
}

// Лучше с memoization
Map<int, int> memo = {};
int fibFast(int n) {
  if (memo.containsKey(n)) return memo[n]!;
  if (n <= 1) return n;
  memo[n] = fibFast(n - 1) + fibFast(n - 2);
  return memo[n]!;
}

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

Для n = 1,000,000 операций:

O(1)      → ~1 операция
O(log n)  → ~20 операций
O(n)      → ~1,000,000 операций
O(n log n)→ ~20,000,000 операций
O(n²)     → ~1,000,000,000,000 операций (ОЧЕНЬ медленно!)
O(2^n)    → невозможно вычислить

Анализ сложности в Flutter

ListView с большим списком:

// ПЛОХО: O(n²) при прокрутке
ListView(
  children: items.map((item) => ExpensiveWidget(item)).toList(),
)

// ХОРОШО: O(n) — ленивая загрузка
ListView.builder(
  itemCount: items.length,
  itemBuilder: (context, index) => ExpensiveWidget(items[index]),
)

Поиск в большом списке:

// ПЛОХО: O(n) каждый раз
List<User> users = [...];
bool found = users.any((u) => u.id == userId);

// ХОРОШО: O(1) поиск
Set<int> userIds = users.map((u) => u.id).toSet();
bool found = userIds.contains(userId);

Построение вложенной структуры:

// ПЛОХО: O(n²)
Map<String, List<Item>> grouped = {};
for (final item in items) {
  if (!grouped.containsKey(item.category)) {
    grouped[item.category] = items.where((i) => i.category == item.category).toList();
  }
}

// ХОРОШО: O(n)
Map<String, List<Item>> grouped = {};
for (final item in items) {
  grouped.putIfAbsent(item.category, () => []).add(item);
}

Space Complexity (Пространственная сложность)

// O(1) — константное пространство
int maxValue(List<int> arr) {
  int max = arr[0];
  for (int num in arr) {
    if (num > max) max = num;
  }
  return max; // Одна переменная
}

// O(n) — линейное пространство
List<int> duplicate(List<int> arr) {
  return [...arr]; // Новый список размером n
}

// O(n²) — квадратичное пространство
List<List<int>> createMatrix(int n) {
  return List.generate(n, (i) => List.generate(n, (j) => 0));
}

Лучшие практики для Flutter разработчика

1. Предпочитайте O(log n) и O(n log n):

// Используй binary search вместо linear search
// Используй quicksort вместо bubble sort

2. Избегайте O(n²) в UI коде:

// Используй ListView.builder вместо ListView с children
// Используй Set для поиска вместо List

3. Профилируйте реальные данные:

// DevTools Performance вкладка показывает реальное время
// Не гадай, измеряй!

4. Помните о памяти на мобильном:

// O(n) память может быть проблемой для больших n
// Streaming большие файлы вместо загрузки всего в памяти

Понимание Big O — это ключ к написанию быстрого и отзывчивого мобильного приложения.