Какая сложность алгоритма перебор?

# Временная сложность алгоритма перебора (брутфорс)

Ответ: O(n)

Времення сложность перебора всех элементов коллекции из n элементов составляет O(n).

Примеры перебора

Перебор массива

int[] array = {1, 2, 3, 4, 5};

// ✅ Простой перебор: O(n)
for (int i = 0; i < array.length; i++) {
    System.out.println(array[i]);
}
// n = 5 итераций

// ✅ For-each: O(n)
for (int num : array) {
    System.out.println(num);
}

Перебор списка

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

// ✅ O(n)
for (String item : list) {
    System.out.println(item);
}

// ✅ Поиск элемента: O(n) в худшем случае
boolean found = false;
for (String item : list) {
    if (item.equals("B")) {
        found = true;
        break;  // Может выйти раньше
    }
}

Усложненные случаи

Вложенные циклы: O(n²)

int[] array = {1, 2, 3, 4, 5};

// ❌ Двойной перебор: O(n²)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        System.out.println(array[i] + ", " + array[j]);
    }
}
// Итераций: 5 * 5 = 25

Три вложенных цикла: O(n³)

// ❌ O(n³)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // операция
        }
    }
}
// Итераций: n * n * n = n³

Перебор с условиями

С ранним выходом: O(n)

int[] array = {1, 2, 3, 4, 5};

// Best case: O(1) - первый элемент
for (int i = 0; i < array.length; i++) {
    if (array[i] == 1) {
        System.out.println("Found!");
        break;  // Выходим сразу
    }
}

// Average case: O(n/2) = O(n)
for (int i = 0; i < array.length; i++) {
    if (array[i] == 3) {
        System.out.println("Found!");
        break;
    }
}

// Worst case: O(n) - элемента нет
for (int i = 0; i < array.length; i++) {
    if (array[i] == 999) {
        System.out.println("Found!");
        break;
    }
}

Перебор в HashMap: O(n)

HashMap<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

// ✅ Перебор всех элементов: O(n)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// n = количество пар в HashMap

Практический пример

public class BruteForce {
    
    // O(n) - простой перебор
    public boolean contains(int[] array, int target) {
        for (int num : array) {
            if (num == target) {
                return true;
            }
        }
        return false;
    }
    
    // O(n²) - поиск пары
    public boolean hasPair(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] + array[j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // O(n³) - поиск тройки
    public boolean hasTriple(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                for (int k = j + 1; k < array.length; k++) {
                    if (array[i] + array[j] + array[k] == target) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

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

Алгоритм                    Сложность
─────────────────────────────────────
Перебор всех элементов      O(n)
Линейный поиск              O(n)
Двойной перебор             O(n²)
Тройной перебор             O(n³)
Перебор с break/continue    O(n) в avg, O(n) в worst
Перебор HashMap/Set         O(n)

Оптимизация от O(n²) к O(n)

// ❌ Неэффективный O(n²)
public boolean hasDuplicate(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

// ✅ Эффективный O(n)
public boolean hasDuplicate(int[] array) {
    Set<Integer> seen = new HashSet<>();
    for (int num : array) {
        if (seen.contains(num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}

Резюме

Перебор n элементов:

• Один цикл: O(n)
• Два цикла вложенные: O(n²)
• Три цикла вложенные: O(n³)
• С ранним выходом: O(n) в worst case
• HashMap/Set: O(n) для полного перебора

Перебор - это самый простой алгоритм, но не всегда самый эффективный.