Как достигается логарифмическая сложность операций

# Как достигается логарифмическая сложность операций

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

Логарифмическая сложность O(log n) достигается путём разделения на половины (divide and conquer). Вместо проверки всех элементов по одному, мы исключаем большую часть возможностей с каждым шагом, что экспоненциально снижает объём работы.

1. Двоичный поиск (Binary Search) - классический пример

Идея

Массив: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Ищем: 13

Шаг 1: Проверяем середину (индекс 5) = 11. 13 > 11, ищем в правой половине
Шаг 2: Проверяем новую середину = 15. 13 < 15, ищем в левой половине
Шаг 3: Проверяем середину = 13. Найдено!

Вместо 10 проверок нужно только 3! Это O(log₂ 10) ≈ 3.3

Реализация

public class BinarySearch {
    // Итеративная версия
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;  // Выбираем середину
            
            if (arr[mid] == target) {
                return mid;  // Найдено
            } else if (arr[mid] < target) {
                left = mid + 1;  // Ищем в правой половине
            } else {
                right = mid - 1;  // Ищем в левой половине
            }
        }
        return -1;  // Не найдено
    }
    
    // Рекурсивная версия
    private static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, right);  // Половинка!
        } else {
            return binarySearchRecursive(arr, target, left, mid - 1);   // Половинка!
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        
        long startTime = System.nanoTime();
        int result = binarySearch(arr, 13);
        long endTime = System.nanoTime();
        
        System.out.println("Результат: " + result);
        System.out.println("Время: " + (endTime - startTime) + " нс");
    }
}

2. Сбалансированные деревья поиска (BST)

Идея

Дерево, где каждое поддерево примерно половину элементов исключает на каждом уровне.

        8
       / \
      4   12
     / \ / \
    2 6 10 14
   / \
  1   3

Для 16 элементов - глубина дерева = log₂(16) = 4

TreeMap в Java

import java.util.TreeMap;
import java.util.Map;

public class TreeMapExample {
    public static void main(String[] args) {
        // TreeMap внутри использует Red-Black дерево (сбалансированное)
        Map<Integer, String> map = new TreeMap<>();
        
        // Все операции O(log n)
        map.put(5, "five");      // O(log n)
        map.put(3, "three");     // O(log n)
        map.put(7, "seven");     // O(log n)
        
        String value = map.get(5);  // O(log n) поиск
        
        // Сравнение с HashMap (O(1) в среднем)
        // TreeMap медленнее, но дает сортированный порядок
        
        System.out.println(map.firstKey());     // Минимум
        System.out.println(map.lastKey());      // Максимум
        System.out.println(map.floorKey(6));    // Наибольший <= 6
        System.out.println(map.ceilingKey(6));  // Наименьший >= 6
    }
}

Red-Black дерево

public class RedBlackTreeConcept {
    /*
     * Red-Black дерево - это самобалансирующееся BST с правилами:
     * 
     * 1. Каждый узел красный или чёрный
     * 2. Корень - чёрный
     * 3. Листья (NIL) - чёрные
     * 4. Красный узел имеет только чёрных потомков
     * 5. От узла к листу одно и то же число чёрных узлов
     * 
     * Это гарантирует:
     * - Дерево примерно сбалансировано
     * - Высота дерева <= 2*log(n+1)
     * - Все операции O(log n)
     */
}

3. Сортировка с логарифмической сложностью

Merge Sort и Quick Sort

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            // Делим на половины (log n уровней)
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            
            // Сливаем (O(n) на каждом уровне)
            merge(arr, left, mid, right);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        // O(n) операция
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        
        System.arraycopy(temp, 0, arr, left, temp.length);
    }
    
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        // O(n log n) = O(7 * 2.8) ≈ 20 операций вместо 49 при пузырьке
    }
}

/*
 * Уровни разбиения:
 * 
 * Уровень 0: [38, 27, 43, 3, 9, 82, 10]        1 кусок
 * Уровень 1: [38, 27] [43, 3] [9, 82] [10]     2 куска
 * Уровень 2: [38][27] [43][3] [9][82] [10]     4 куска
 * Уровень 3: (merge обратно)                    O(n) на каждом
 * 
 * Глубина = log₂(7) ≈ 3
 * Итого: 3 * 7 = 21 операция
 */

4. Приоритетная очередь (Heap)

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // Heap = бинарное дерево, где родитель <= потомков
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // Все операции O(log n)
        minHeap.offer(5);     // O(log n) добавление
        minHeap.offer(3);     // O(log n)
        minHeap.offer(7);     // O(log n)
        minHeap.offer(1);     // O(log n)
        
        System.out.println(minHeap.poll());  // O(log n) - удалить минимум
        
        // Структура:
        //       1
        //      / \
        //     3   5
        //    /
        //   7
        //
        // Высота log n для n элементов
    }
}

5. Поиск в графе (BFS, DFS)

import java.util.*;

public class GraphSearch {
    static class Graph {
        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
        
        public void binarySearch(int nodes) {
            // BFS может быть O(log n) если граф имеет специальную структуру
            // Например, в дереве с ветвлением 2 (бинарное дерево)
            // высота = log n
        }
    }
}

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

public class ComplexityComparison {
    public static void main(String[] args) {
        // n = 1,000,000
        
        long O_n = 1_000_000;                    // 1 миллион
        long O_log_n = (long)(Math.log(1_000_000) / Math.log(2));  // ~20
        long O_n_log_n = 1_000_000 * 20;         // 20 миллионов
        long O_n2 = 1_000_000_000_000L;          // 1 триллион
        
        System.out.println("O(1): 1");
        System.out.println("O(log n): " + O_log_n);           // 20
        System.out.println("O(n): " + O_n);                   // 1,000,000
        System.out.println("O(n log n): " + O_n_log_n);       // 20,000,000
        System.out.println("O(n²): " + O_n2);                 // 1,000,000,000,000
        
        // На современном компьютере (1 млрд операций/сек):
        // O(log n): 0.00002 сек
        // O(n): 1 сек
        // O(n log n): 20 сек
        // O(n²): 1 миллион сек
    }
}

7. Ключевой механизм: деление пополам

public class RecursionDepth {
    static class Counter {
        int depth = 0;
        
        int divideByHalf(int n) {
            depth++;
            if (n <= 1) return depth;
            return divideByHalf(n / 2);
        }
    }
    
    public static void main(String[] args) {
        Counter counter = new Counter();
        
        int depth1 = counter.divideByHalf(8);     // 3 (log₂ 8)
        int depth2 = counter.divideByHalf(1024);  // 10 (log₂ 1024)
        int depth3 = counter.divideByHalf(1_000_000);  // 20 (log₂ 1M)
        
        System.out.println("8: " + depth1);       // 3
        System.out.println("1024: " + depth2);    // 10
        System.out.println("1M: " + depth3);      // 20
    }
}

Резюме

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

1. Двоичный поиск - исключаем половину элементов на каждом шаге
2. Сбалансированные деревья - высота ~log n для n элементов
3. Разделяй и властвуй - делим задачу на равные части
4. Heap операции - балансирующее дерево с высотой log n
5. N log N сортировки - комбинация разбиения (log n) и слияния (n)

Ключ: каждый шаг исключает примерно половину оставшихся возможностей.