В этом уроке ты
- Узнаешь, что такое метод полного перебора (bruteforce) и где он применяется.
- Научишься использовать bruteforce для поиска всех возможных решений задачи.
- Разберёшься, как оценивать время и память, затрачиваемые на полный перебор.
Полный перебор (Bruteforce)
Полный перебор (bruteforce) — это метод решения задачи, при котором последовательно перебираются все возможные комбинации без какой-либо оптимизации.
Пример из жизни
Представь, что ты забыл пароль от телефона, но знаешь, что он состоит из трёх цифр. Единственный способ узнать пароль — проверить все возможные варианты: 000, 001, 002, …, 999
Этот метод гарантированно найдёт верное решение, но он может занимать очень много времени, когда количество комбинаций слишком велико.
Bruteforce на собеседованиях
Полный перебор на практике используют редко из-за его неэффективности. Однако существует класс задач, для которых не существует более быстрого алгоритма, кроме как проверить все варианты.
Перебор всех n-значных паролей
Ниже приведён пример кода, который перебирает все возможные n-значные комбинации, если пароль может содержать только цифры 0, 1 и 2:
class Solution
{
static void BruteForceHelper(List<int> curr, int n, List<List<int>> result)
{
if (curr.Count == n)
{
// Нашли полную комбинацию, добавляем в результат
result.Add(new List<int>(curr)); // Копируем список, чтобы избежать изменений
return;
}
// Перебираем возможные цифры: 0, 1, 2
for (int i = 0; i < 3; i++)
{
// Добавляем число в текущую последовательность
curr.Add(i);
// Рекурсивный вызов для следующего шага
BruteForceHelper(curr, n, result);
// Убираем последнее число (откат назад)
curr.RemoveAt(curr.Count - 1);
}
}
// Время: O(3^n)
// Память: O(3^n)
public static void BruteForce(int n)
{
List<List<int>> result = new List<List<int>>();
BruteForceHelper(new List<int>(), n, result);
// Выводим все возможные комбинации
foreach (var combo in result)
{
foreach (var num in combo)
{
Console.Write(num);
}
Console.WriteLine();
}
}
// Запуск перебора для 3-значного кода (000 - 222)
static void Main()
{
BruteForce(3);
}
}#include <iostream>
#include <vector>
using namespace std;
void bruteForceHelper(vector<int>& curr, int n, vector<vector<int>>& result) {
if (curr.size() == n) {
// Нашли полную комбинацию, добавляем в результат
result.push_back(curr); // Копируем список, чтобы избежать изменений
return;
}
// Перебираем возможные цифры: 0, 1, 2
for (int i = 0; i < 3; ++i) {
// Добавляем число в текущую последовательность
curr.push_back(i);
// Рекурсивный вызов для следующего шага
bruteForceHelper(curr, n, result);
// Убираем последнее число (откат назад)
curr.pop_back();
}
}
// Время: O(3^n)
// Память: O(3^n)
void bruteForce(int n) {
vector<vector<int>> result;
vector<int> curr;
bruteForceHelper(curr, n, result);
// Выводим все возможные комбинации
for (const auto& combo : result) {
for (int num : combo) {
cout << num;
}
cout << endl;
}
}
// Запуск перебора для 3-значного кода (000 - 222)
int main() {
bruteForce(3);
return 0;
}package main
func bruteForceHelper(curr []int, n int, result *[][]int) {
if len(curr) == n {
// Нашли полную комбинацию, добавляем в результат
combination := make([]int, n)
copy(combination, curr) // Копируем список, чтобы избежать изменений
*result = append(*result, combination)
return
}
// Перебираем возможные цифры: 0, 1, 2
for i := 0; i < 3; i++ {
// Добавляем число в текущую последовательность
curr = append(curr, i)
// Рекурсивный вызов для следующего шага
bruteForceHelper(curr, n, result)
// Убираем последнее число (откат назад)
curr = curr[:len(curr)-1]
}
}
// Время: O(3^n)
// Память: O(3^n)
func bruteForce(n int) {
var result [][]int
bruteForceHelper([]int{}, n, &result)
// Выводим все возможные комбинации
for _, combo := range result {
for _, num := range combo {
fmt.Print(num)
}
fmt.Println()
}
}
// Запуск перебора для 3-значного кода (000 - 222)
func main() {
bruteForce(3)
}import java.util.*;
public class Solution {
public static void bruteForceHelper(List<Integer> curr, int n, List<List<Integer>> result) {
if (curr.size() == n) {
// Нашли полную комбинацию, добавляем в результат
result.add(new ArrayList<>(curr)); // Копируем список, чтобы избежать изменений
return;
}
// Перебираем возможные цифры: 0, 1, 2
for (int i = 0; i < 3; i++) {
// Добавляем число в текущую последовательность
curr.add(i);
// Рекурсивный вызов для следующего шага
bruteForceHelper(curr, n, result);
// Убираем последнее число (откат назад)
curr.remove(curr.size() - 1);
}
}
// Время: O(3^n)
// Память: O(3^n)
public static void bruteForce(int n) {
List<List<Integer>> result = new ArrayList<>();
bruteForceHelper(new ArrayList<>(), n, result);
// Выводим все возможные комбинации
for (List<Integer> combo : result) {
for (int num : combo) {
System.out.print(num);
}
System.out.println();
}
}
// Запуск перебора для 3-значного кода (000 - 222)
public static void main(String[] args) {
bruteForce(3);
}
}from typing import List
def bruteforce_helper(curr: List[int], n: int, result: List[List[int]]) -> None:
if len(curr) == n:
# Нашли полную комбинацию, добавляем в результат
result.append(curr[:]) # Копируем список, чтобы избежать изменений
return
# Перебираем возможные цифры: 0, 1, 2
for i in range(3):
# Добавляем число в текущую последовательность
curr.append(i)
# Рекурсивный вызов для следующего шага
bruteforce_helper(curr, n, result)
# Убираем последнее число (откат назад)
curr.pop()
# Время: O(3^n)
# Память: O(3^n)
def bruteforce(n: int) -> None:
result = []
bruteforce_helper([], n, result)
# Выводим все возможные комбинации
for combo in result:
print("".join(map(str, combo)))
# Запуск перебора для 3-значного кода (000 - 222)
bruteforce(3)export function bruteForceHelper(curr, n, result) {
if (curr.length === n) {
// Нашли полную комбинацию, добавляем в результат
result.push([...curr]); // Копируем список, чтобы избежать изменений
return;
}
// Перебираем возможные цифры: 0, 1, 2
for (let i = 0; i < 3; i++) {
// Добавляем число в текущую последовательность
curr.push(i);
// Рекурсивный вызов для следующего шага
bruteForceHelper(curr, n, result);
// Убираем последнее число (откат назад)
curr.pop();
}
}
// Время: O(3^n)
// Память: O(3^n)
export function bruteForce(n) {
let result = [];
bruteForceHelper([], n, result);
// Выводим все возможные комбинации
for (let combo of result) {
console.log(combo.join(""));
}
}
// Запуск перебора для 3-значного кода (000 - 222)
bruteForce(3);Визуализация полного перебора
Bruteforce можно представить в виде дерева решений, где каждая ветвь соответствует выбору новой цифры на очередном шаге.
Оценка времени и памяти полного перебора
Рассмотрим пример с 4-значным кодом, где каждая цифра может принимать значения от 0 до 9: Количество возможных комбинаций: 10 * 10 * 10 * 10 = 10^4 = 10 000.
Если же мы возьмём 100-значный код, в котором каждая цифра может быть только 0 или 1, количество вариантов равно 2^100 = 1,26 * 10^30 . Перебрать все эти комбинации за разумное время невозможно на обычном компьютере. Если взять средний компьютер, то перебор 1,26 * 10^30 вариантов займет десятки тысяч лет!
Обобщённая оценка сложности:
- Время:
O(n^m), гдеn— количество возможных значений для каждого символа, аm— длина комбинации. - Память:
O(n^m), если мы хотим хранить все варианты сразу.
Такая зависимость от n^m
Когда использовать bruteforce?
Bruteforce может подойти, если:
- Количество вариантов не слишком велико. Тогда перебор всех решений занимает разумное время.
- Задачу нельзя решить быстрее никакими другими методами (или оптимизация не оправдана для конкретной ситуации).
Что дальше
Теперь ты знаешь, что такое bruteforce, как он реализуется и почему его выполнение может быть долгим. В следующем уроке ты рассмотришь задачу с реального собеседования в Big Tech и попробуешь применить полученные знания на практике.