Приведи пример любого алгоритма и его алгоритмической сложности

Примеры алгоритмов и их алгоритмической сложности (Big O)

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

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

// O(1): время не зависит от размера данных

int getFirstElement(List<int> list) {
  return list[0];  // Всегда один шаг!
}

bool checkDictionary(Map<String, int> dict, String key) {
  return dict.containsKey(key);  // Hash lookup = O(1)
}

int findInArray(List<int> arr, int target) {
  // Если массив sorted и используем binary search
  // Но для случайного доступа = O(1)
  return arr[5];  # Всегда один шаг
}

// Примеры O(1) операций:
// - Доступ к элементу по индексу
// - Вставка/удаление в конец массива
// - Hash map lookup/insert/delete
// - Простые операции (a + b, if, return)

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

// O(log n): время логарифмически зависит от размера

// Binary Search: поиск в отсортированном массиве
int binarySearch(List<int> sortedList, int target) {
  int left = 0, right = sortedList.length - 1;
  
  while (left <= right) {
    int mid = (left + right) ~/ 2;
    
    if (sortedList[mid] == target) {
      return mid;  # Найден!
    } else if (sortedList[mid] < target) {
      left = mid + 1;  # Ищем в правой половине
    } else {
      right = mid - 1;  # Ищем в левой половине
    }
  }
  
  return -1;  # Не найден
}

// Сложность анализ:
// n = 1000000 → max 20 итераций (log2(1000000) ≈ 20)
// n = 1000000000 → max 30 итераций
// ОЧЕНЬ эффективно!

void main() {
  final nums = [1, 3, 5, 7, 9, 11, 13, 15];
  
  print(binarySearch(nums, 7));   # 3 → найден
  print(binarySearch(nums, 10));  # -1 → не найден
}

// Примеры O(log n) операций:
// - Binary search
// - Tree operations (balanced)
// - Divide and conquer

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

// O(n): время линейно зависит от размера

// Linear Search: поиск в неотсортированном массиве
int linearSearch(List<int> list, int target) {
  for (int i = 0; i < list.length; i++) {
    if (list[i] == target) {
      return i;  # Найден
    }
  }
  return -1;  # Не найден
}

// Сложность:
// n = 1000 → max 1000 итераций
// n = 1000000 → max 1000000 итераций
// Линейный рост

// Сумма элементов массива
int sumArray(List<int> arr) {
  int sum = 0;
  for (int num in arr) {  # O(n) цикл
    sum += num;
  }
  return sum;
}

// Примеры O(n) операций:
// - Простой цикл по массиву
// - Linear search
// - Итерация по коллекции
// - Map и filter

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

// O(n log n): очень распространено в сортировке

// Merge Sort: эффективная сортировка
List<int> mergeSort(List<int> arr) {
  if (arr.length <= 1) return arr;  # Base case
  
  int mid = arr.length ~/ 2;
  List<int> left = mergeSort(arr.sublist(0, mid));  # Рекурсия O(log n)
  List<int> right = mergeSort(arr.sublist(mid));     # Рекурсия O(log n)
  
  return merge(left, right);  # Слияние O(n)
}

List<int> merge(List<int> left, List<int> right) {
  List<int> result = [];
  int i = 0, j = 0;
  
  while (i < left.length && j < right.length) {  # O(n)
    if (left[i] <= right[j]) {
      result.add(left[i++]);
    } else {
      result.add(right[j++]);
    }
  }
  
  result.addAll(left.sublist(i));
  result.addAll(right.sublist(j));
  return result;
}

// Анализ:
// n = 8:    8 * log2(8) = 8 * 3 = 24 операций
// n = 1000: 1000 * log2(1000) ≈ 10000 операций
// Очень эффективно!

void main() {
  final nums = [5, 2, 8, 1, 9];
  final sorted = mergeSort(nums);
  print(sorted);  # [1, 2, 5, 8, 9]
}

// Примеры O(n log n) операций:
// - Merge Sort
// - Quick Sort (среднее)
// - Heap Sort
// - Tree operations (balance)

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

// O(n²): два вложенных цикла

// Bubble Sort: простая, но неэффективная сортировка
List<int> bubbleSort(List<int> arr) {
  List<int> result = List<int>.from(arr);
  
  for (int i = 0; i < result.length; i++) {        # O(n) цикл
    for (int j = 0; j < result.length - i - 1; j++) { # O(n) вложенный цикл
      if (result[j] > result[j + 1]) {
        // Swap
        int temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
      }
    }
  }
  
  return result;
}

// Сложность:
// n = 100:     100² = 10000 операций
// n = 1000:    1000² = 1000000 операций!
// n = 10000:   10000² = 100000000 операций!!
// Очень медленно при больших данных

// Вложенный цикл без сортировки
bool hasDuplicate(List<int> arr) {
  for (int i = 0; i < arr.length; i++) {     # O(n)
    for (int j = i + 1; j < arr.length; j++) {  # O(n)
      if (arr[i] == arr[j]) {  # Проверка O(1)
        return true;
      }
    }
  }
  return false;
}

// Примеры O(n²) операций:
// - Bubble Sort
// - Insertion Sort
// - Selection Sort
// - Вложенные циклы

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

// O(2^n): ужасно медленно!

// Fibonacci: наивная рекурсивная реализация
int fibonacciNaive(int n) {
  if (n <= 1) return n;
  
  return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
  # Каждый вызов создаёт 2 вызова
  # 2^n операций!
}

// Дерево вызовов для fib(5):
// fib(5) = fib(4) + fib(3)
// = (fib(3) + fib(2)) + (fib(2) + fib(1))
// = ...
// ~32 вызова для n=5!
// ~1000000 вызовов для n=30!!

print(fibonacciNaive(5));   # 5 → быстро
print(fibonacciNaive(20));  # 6765 → медленно
print(fibonacciNaive(40));  # зависнет...

// ✅ Лучше: Динамическое программирование O(n)
int fibonacciOptimized(int n) {
  if (n <= 1) return n;
  
  List<int> dp = List<int>.filled(n + 1, 0);
  dp[1] = 1;
  
  for (int i = 2; i <= n; i++) {  # O(n) цикл
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

print(fibonacciOptimized(40));  # Мгновенно!

// Примеры O(2^n) операций:
// - Наивная рекурсия
// - Subset generation
// - Permutations
// ИЗБЕГАЙ!

O(n!) — Факториальная сложность

// O(n!): еще хуже, чем экспоненциальная

// Перестановки (permutations)
List<List<int>> permutations(List<int> arr) {
  if (arr.length <= 1) return [arr];
  
  List<List<int>> result = [];
  
  for (int i = 0; i < arr.length; i++) {
    int current = arr[i];
    List<int> remaining = [...arr.sublist(0, i), ...arr.sublist(i + 1)];
    
    for (final perm in permutations(remaining)) {
      result.add([current, ...perm]);
    }
  }
  
  return result;
}

// Сложность:
// n = 5:  5! = 120 перестановок → быстро
// n = 10: 10! = 3628800 перестановок → медленно
// n = 12: 12! = 479001600 перестановок → очень медленно
// n = 15: 15! = ~1 триллион → невозможно

print(permutations([1, 2, 3]).length);  # 6
print(permutations([1, 2, 3, 4]).length);  # 24
// permutations([1, 2, 3, 4, 5]);  # 120 — ещё окей
// permutations(List<int>.generate(15, (i) => i));  # НИКОГДА!

// Примеры O(n!) операций:
// - Перестановки
// - Брутфорс комбинации
// - Некоторые NP-complete задачи
// АБСОЛЮТНО ИЗБЕГАЙ!

Таблица сравнения сложностей

Сложность    | n=10  | n=100    | n=1000    | n=10000
─────────────┼───────┼──────────┼───────────┼───────────
O(1)         | 1     | 1        | 1         | 1
O(log n)     | 3     | 7        | 10        | 13
O(n)         | 10    | 100      | 1000      | 10000
O(n log n)   | 30    | 700      | 10000     | 130000
O(n²)        | 100   | 10000    | 1000000   | 100000000
O(2^n)       | 1024  | 10^30    | 10^300    | 10^3000
O(n!)        | 3M    | 10^157   | 10^2567   | 10^35659

Вывод: Старайся достичь O(1), O(log n) или O(n)

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

// ✅ Хорошо: O(n)
class UserListViewModel {
  List<User> filterUsers(List<User> users, String query) {
    return users.where(
      (user) => user.name.toLowerCase().contains(query.toLowerCase()),
    ).toList();  # O(n)
  }
}

// ❌ Плохо: O(n²)
class BadUserListViewModel {
  List<User> filterUsers(List<User> users, String query) {
    List<User> result = [];
    
    for (final user in users) {         # O(n)
      for (final char in query) {       # O(m) — вложенный!
        if (user.name.contains(char)) {
          result.add(user);
          break;
        }
      }
    }
    
    return result;  # O(n*m)
  }
}

// ✅ Хорошо: O(n)
class EfficientSearch {
  List<User> searchUsers(List<User> users, String query) {
    // Используй регулярное выражение или простой contains
    return users
      .where((u) => u.name.toLowerCase().contains(query.toLowerCase()))
      .toList();
  }
}

// ❌ Плохо: O(n²) для больших списков
final displayedUsers = allUsers.map((user) {
  // Если в этом блоке O(n) операция — итого O(n²)!
  final permissions = userPermissions.where((p) => p.userId == user.id).toList();
  return UserDisplayModel(user: user, permissions: permissions);
}).toList();

// ✅ Хорошо: O(n)
final permissionMap = Map.fromIterable(
  userPermissions,
  key: (p) => p.userId,
  value: (p) => p,
);

final displayedUsers = allUsers.map((user) {
  final permissions = permissionMap[user.id] ?? [];
  return UserDisplayModel(user: user, permissions: permissions);
}).toList();

Резюме

Big O сложности (от лучшей к худшей):

1. O(1) — идеально (доступ по индексу, hash lookup)
2. O(log n) — отлично (binary search)
3. O(n) — хорошо (простой цикл)
4. O(n log n) — приемлемо (merge sort)
5. O(n²) — медленно (bubble sort, вложенные циклы)
6. O(2^n) — очень медленно (наивная рекурсия)
7. O(n!) — невозможно (перестановки)

Best Practice:

• ✅ Анализируй сложность алгоритмов
• ✅ Используй структуры данных правильно
• ✅ Избегай вложенных циклов
• ✅ Используй мемоизацию для рекурсии
• ✅ Профилируй код перед оптимизацией