public class InputMemoryExample {
    // Метод суммирует элементы массива
    // Память: O(n) для хранения входного массива
    public static int sumArray(int[] array) {
        int sum = 0;
        for (int value : array) {
            sum += value;
        }
        return sum;
    }
    
    // Метод создает копию массива
    // Память: O(n) для входных данных + O(n) для копии = O(n)
    public static int[] copyAndModify(int[] array) {
        int[] copy = new int[array.length]; // Дополнительная память O(n)
        for (int i = 0; i < array.length; i++) {
            copy[i] = array[i] * 2;
        }
        return copy;
    }
}

public class AuxiliaryStructures {
    // Алгоритм поиска двух чисел с заданной суммой
    // Версия 1: Без дополнительной памяти, но O(n²) времени
    public static int[] findPairNaive(int[] array, int targetSum) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] + array[j] == targetSum) {
                    return new int[]{array[i], array[j]};
                }
            }
        }
        return null; // Память: O(1) вспомогательной
    }
    
    // Версия 2: С хеш-таблицей, O(n) времени, но O(n) памяти
    public static int[] findPairOptimized(int[] array, int targetSum) {
        Set<Integer> seen = new HashSet<>(); // Вспомогательная структура O(n)
        for (int num : array) {
            int complement = targetSum - num;
            if (seen.contains(complement)) {
                return new int[]{complement, num};
            }
            seen.add(num);
        }
        return null;
    }
}

public class RecursionMemory {
    // Рекурсивное вычисление факториала
    // Пространственная сложность: O(n) из-за глубины рекурсии
    public static long factorialRecursive(int n) {
        if (n <= 1) return 1;
        return n * factorialRecursive(n - 1); // Каждый вызов добавляет фрейм в стек
    }
    
    // Итеративное вычисление факториала
    // Пространственная сложность: O(1)
    public static long factorialIterative(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    
    // Рекурсивный обход дерева в глубину (DFS)
    // Пространственная сложность: O(h), где h - высота дерева
    public static void dfs(TreeNode node) {
        if (node == null) return;
        
        // Обработка узла
        System.out.println(node.value);
        
        // Рекурсивный обход детей
        dfs(node.left);
        dfs(node.right);
        
        // В худшем случае (вырожденное дерево) h = n, сложность O(n)
        // В сбалансированном дереве h = log n, сложность O(log n)
    }
}

public class HashTableAnalysis {
    // HashMap обеспечивает в среднем O(1) для операций put, get, remove
    // Но требует значительной дополнительной памяти
    public static void hashTableDemo() {
        Map<String, Integer> hashMap = new HashMap<>(1000);
        
        // Вставка: вычисление хеша O(1) + обработка коллизий
        hashMap.put("key1", 100);
        hashMap.put("key2", 200);
        
        // Поиск: вычисление хеша O(1) + доступ к bucket
        Integer value = hashMap.get("key1");
        
        // Память: массив buckets (capacity) + узлы для пар ключ-значение
        // Коэффициент загрузки (load factor) по умолчанию 0.75
        // При capacity=16 и 12 элементах массив будет расширен
    }
}

public class SortedListAnalysis {
    // TreeMap обеспечивает O(log n) для операций
    // Но требует меньше дополнительной памяти
    public static void sortedMapDemo() {
        // TreeMap основан на красно-черном дереве
        Map<String, Integer> treeMap = new TreeMap<>();
        
        // Вставка: O(log n) для поиска позиции + O(1) для вставки (с балансировкой)
        treeMap.put("key1", 100);
        treeMap.put("key2", 200);
        
        // Поиск: O(log n) для обхода дерева
        Integer value = treeMap.get("key1");
        
        // Память: только узлы дерева, без массива buckets
        // Каждый узел содержит ссылки на детей, цвет, ключ и значение
    }
    
    // Альтернатива: отсортированный ArrayList с бинарным поиском
    public static class SortedArrayList<K extends Comparable<K>, V> {
        private List<Entry<K, V>> list = new ArrayList<>();
        
        // Вставка с поддержанием порядка: O(n) для поиска позиции + O(n) для сдвига
        public void put(K key, V value) {
            int index = Collections.binarySearch(
                list.stream().map(e -> e.key).collect(Collectors.toList()), 
                key
            );
            
            if (index >= 0) {
                list.set(index, new Entry<>(key, value));
            } else {
                int insertionPoint = -index - 1;
                list.add(insertionPoint, new Entry<>(key, value));
            }
        }
        
        // Поиск: O(log n) бинарным поиском
        public V get(K key) {
            int index = Collections.binarySearch(
                list.stream().map(e -> e.key).collect(Collectors.toList()), 
                key
            );
            return index >= 0 ? list.get(index).value : null;
        }
    }
}

// Упрощенная реализация ArrayList для демонстрации принципов
public class AmortizedArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    private Object[] elementData;
    private int size;
    
    public AmortizedArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }
    
    // Амортизированная сложность добавления: O(1)
    public boolean add(E element) {
        ensureCapacityInternal(size + 1);  // Может вызвать дорогое расширение
        elementData[size++] = element;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (minCapacity - elementData.length > 0) {
            // Требуется расширение массива
            grow(minCapacity);
        }
    }
    
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        
        // Стандартная стратегия роста: увеличение на 50%
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        
        // Самая дорогая операция: копирование всех элементов
        elementData = Arrays.copyOf(elementData, newCapacity);
        
        // В этот момент выполняется O(n) операций
        // Но эта стоимость распределяется (амортизируется) по предыдущим дешевым операциям
    }
    
    // Метод получения элемента: всегда O(1)
    @SuppressWarnings("unchecked")
    public E get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (E) elementData[index];
    }
}

// Плохо: множественные расширения при добавлении 1000 элементов
List<Integer> list = new ArrayList<>(); // capacity=10
for (int i = 0; i < 1000; i++) {
    list.add(i); // Расширения при 10...
}

// Хорошо: одно расширение или вообще без расширений
List<Integer> optimizedList = new ArrayList<>(1000); // capacity=1000
for (int i = 0; i < 1000; i++) {
    optimizedList.add(i); // Без расширений
}

public class CacheTradeoff {
    // LRU (Least Recently Used) кэш
    // Использует больше памяти для поддержания порядка доступа
    public static class LRUCache<K, V> {
        private final int capacity;
        private final Map<K, V> map;
        private final Deque<K> accessOrder;
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<>(capacity);
            this.accessOrder = new LinkedList<>();
        }
        
        public V get(K key) {
            V value = map.get(key);
            if (value != null) {
                // Обновляем порядок: O(n) операция
                accessOrder.remove(key);
                accessOrder.addFirst(key);
            }
            return value;
        }
        
        public void put(K key, V value) {
            if (map.size() >= capacity) {
                // Удаляем наименее использованный
                K lruKey = accessOrder.removeLast();
                map.remove(lruKey);
            }
            map.put(key, value);
            accessOrder.addFirst(key);
        }
    }
    
    // Простой кэш с фиксированным размером
    // Использует меньше памяти, но может иметь хуже hit ratio
    public static class SimpleCache<K, V> {
        private final Map<K, V> map;
        private final int maxSize;
        
        public SimpleCache(int maxSize) {
            this.maxSize = maxSize;
            this.map = new HashMap<>(maxSize);
        }
        
        public V get(K key) {
            return map.get(key); // O(1), но нет обновления порядка
        }
        
        public void put(K key, V value) {
            if (map.size() >= maxSize) {
                // Удаляем случайный элемент (на практике сложнее)
                Iterator<K> it = map.keySet().iterator();
                if (it.hasNext()) {
                    map.remove(it.next());
                }
            }
            map.put(key, value);
        }
    }
}

public class CompressionTradeoff {
    // Быстрое сжатие (LZ4), но меньшая степень сжатия
    public byte[] compressFast(byte[] data) {
        // LZ4: высокая скорость, средняя степень сжатия
        // Подходит для компрессии "на лету"
        return lz4Compress(data);
    }
    
    // Медленное сжатие (Zstandard с высоким уровнем), но лучшее сжатие
    public byte[] compressHigh(byte[] data) {
        // Zstandard уровень 19: медленно, но максимальное сжатие
        // Подходит для архивов, где сжатие выполняется один раз
        return zstdCompress(data, 19);
    }
    
    // Выбор стратегии в зависимости от контекста
    public byte[] compressAdaptive(byte[] data, boolean prioritizeSpeed) {
        if (prioritizeSpeed) {
            return compressFast(data); // Для сетевой передачи
        } else {
            return compressHigh(data); // Для долговременного хранения
        }
    }
}

import java.util.TreeSet;

public class Task130126 {
    static class Item130126 implements Comparable<Item130126> {
        int value;
        Item130126(int value) { this.value = value; }
        
        public int compareTo(Item130126 other) {
            return Integer.compare(this.value, other.value);
        }
    }
    public static void main(String[] args) {
        TreeSet<Item130126> set = new TreeSet<>();
        Item130126 item1 = new Item130126(1);
        Item130126 item2 = new Item130126(2);
        set.add(item1);
        set.add(item2);
        item1.value = 3;
        System.out.println(set.contains(item1));
        System.out.println(set.contains(item2));
        set.remove(item1);
        System.out.println(set.size());
    }
}

public class LinearSearch {
    public static int find(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i; // Элемент найден
            }
        }
        return -1; // Элемент отсутствует
    }
    
    // Универсальная версия для любых Comparable объектов
    public static <T extends Comparable<T>> int findGeneric(T[] array, T target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i].compareTo(target) == 0) {
                return i;
            }
        }
        return -1;
    }
}

// Для List интерфейса
List<String> list = Arrays.asList("A", "B", "C", "D");
int index = list.indexOf("C"); // Линейный поиск

// Для массивов через Collections
String[] array = {"A", "B", "C", "D"};
int pos = Collections.indexOf(Arrays.asList(array), "C");

// Использование Stream API (также линейный поиск)
Optional<String> result = Stream.of(array)
    .filter(s -> s.equals("C"))
    .findFirst();

public static int findInt(int[] array, int target) {
    // Развернутый цикл для потенциальной оптимизации JIT-компилятором
    int len = array.length;
    for (int i = 0; i < len; i++) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}

import java.util.*;

public class Task140126 {
    public static void main(String[] args) {
        List<Double> list = Arrays.asList(1.0, 2.0, 3.0, Double.NaN, 4.0);
        
        int index1 = list.indexOf(Double.NaN);
        int index2 = list.lastIndexOf(Double.NaN);
        int index3 = list.indexOf(Double.valueOf(Double.NaN));
        boolean contains = list.contains(Double.NaN);
        
        System.out.println(index1 + " " + index2 + " " + index3 + " " + contains);
    }
}

public class ExtremumFinder {
    public static MinMax findMinMax(int[] arr) {
        int min = arr[0], max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }
        return new MinMax(min, max);
    }
}

Оптимизация: обработка элементов парами уменьшает количество сравнений с 2n до 3n/2. Вместо сравнения каждого элемента с обоими экстремумами, сначала сравниваем пару элементов между собой, затем меньший — с минимумом, больший — с максимумом.

public long sum(int[] arr) {
    long total = 0;  // long для избежания переполнения
    for (int value : arr) {
        total += value;
    }
    return total;
}

public long countPositive(int[] arr) {
    long count = 0;
    for (int value : arr) {
        if (value > 0) count++;
    }
    return count;
}

public static int[] findTwoOldest(int[] years) {
    if (years.length < 2) throw new IllegalArgumentException();
    
    // Инициализируем упорядоченно
    int oldest = Math.min(years[0], years[1]);
    int secondOldest = Math.max(years[0], years[1]);
    
    for (int i = 2; i < years.length; i++) {
        if (years[i] < oldest) {
            secondOldest = oldest;
            oldest = years[i];
        } else if (years[i] < secondOldest) {
            secondOldest = years[i];
        }
    }
    return new int[]{oldest, secondOldest};
}

Особенность: алгоритм корректно обрабатывает дубликаты и все возможные порядки следования элементов. Сложность — O(n) с ровно n-1 сравнениями в худшем случае.

public class Statistics {
    public static Stats compute(int[] data) {
        double mean = 0, m2 = 0; // m2 - сумма квадратов отклонений
        int n = 0;
        
        for (int x : data) {
            n++;
            double delta = x - mean;
            mean += delta / n;
            m2 += delta * (x - mean);
        }
        
        double variance = (n > 1) ? m2 / (n - 1) : 0;
        return new Stats(mean, variance);
    }
}

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

public static String mostFrequentAuthor(String[] authors) {
    Map<String, Integer> freq = new HashMap<>();
    String mostFreq = null;
    int maxCount = 0;
    
    for (String author : authors) {
        int count = freq.getOrDefault(author, 0) + 1;
        freq.put(author, count);
        
        if (count > maxCount) {
            maxCount = count;
            mostFreq = author;
        }
    }
    return mostFreq;
}

public static String majorityElement(String[] arr) {
    String candidate = null;
    int count = 0;
    
    for (String s : arr) {
        if (count == 0) {
            candidate = s;
            count = 1;
        } else if (s.equals(candidate)) {
            count++;
        } else {
            count--;
        }
    }
    
    // Второй проход для проверки (тоже O(n))
    return candidate; // если гарантировано наличие большинства
}

public class CombinedStats {
    int min, max, count;
    long sum;
    
    public void process(int value) {
        if (value < min) min = value;
        if (value > max) max = value;
        sum += value;
        count++;
    }
    
    public double average() {
        return (double) sum / count;
    }
}
Такой подход особенно ценен при обработке потоковых данных, где невозможно хранить историю.

import java.util.List;

public class Task150126 {
    public static void main(String[] args) {
        List<String> data = List.of("A", "B", "C");

        long count = data.stream()
            .peek(s -> System.out.print(s))
            .map(s -> s + s)
            .count();

        System.out.print(count);
    }
}