Что такое logn?

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

Логарифмическая временная сложность O(log n) — это сложность алгоритма, при которой время выполнения растёт логарифмически в зависимости от размера входных данных. Это означает, что при увеличении входных данных в 2 раза, время выполнения увеличивается всего на одну единицу.

Математическое определение

// O(log n) — время растёт как логарифм n
// Если n = 1000, то log₂(1000) ≈ 10
// Если n = 1000000, то log₂(1000000) ≈ 20
// Увеличилось всего в 2 раза при увеличении n в 1000 раз!

Классический пример: Бинарный поиск

Бинарный поиск в отсортированном массиве — это классический пример O(log n):

public class BinarySearch {
    // Бинарный поиск - O(log n)
    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; // Не найдено
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        
        // Массив из 10 элементов
        // Максимум 4 итерации (log₂(10) ≈ 3.3)
        System.out.println(binarySearch(arr, 7)); // Output: 3
        System.out.println(binarySearch(arr, 20)); // Output: -1
    }
}

Другие примеры O(log n)

Поиск в BST (Binary Search Tree):

public class BinarySearchTree {
    public class Node {
        int value;
        Node left, right;
        
        Node(int value) {
            this.value = value;
        }
    }
    
    private Node root;
    
    // Поиск в BST - O(log n) в среднем случае
    public Node search(Node node, int target) {
        if (node == null) return null;
        
        if (target == node.value) {
            return node;
        } else if (target < node.value) {
            return search(node.left, target);
        } else {
            return search(node.right, target);
        }
    }
}

Поиск степени числа:

public class PowerSearch {
    // Найти x^n - O(log n)
    public static long power(long x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        
        // Если n чётное
        if (n % 2 == 0) {
            long half = power(x, n / 2);
            return half * half;
        } else {
            // Если n нечётное
            return x * power(x, n - 1);
        }
    }
    
    public static void main(String[] args) {
        // 2^16 требует O(log 16) = 4 операции
        System.out.println(power(2, 16)); // Output: 65536
    }
}

Сравнение временных сложностей

// Для n = 1000000 элементов:
// O(1)       - 1 операция
// O(log n)   - 20 операций (примерно)
// O(n)       - 1000000 операций
// O(n log n) - 20000000 операций
// O(n²)      - 1000000000000 операций (триллион!)
// O(2ⁿ)      - невообразимое количество операций

public class ComplexityComparison {
    public static void main(String[] args) {
        int n = 1000000;
        
        // O(1)
        long const_ops = 1;
        
        // O(log n) - основание 2
        long log_ops = (long) (Math.log(n) / Math.log(2));
        
        // O(n)
        long linear_ops = n;
        
        // O(n log n)
        long nlogn_ops = n * log_ops;
        
        System.out.println("O(1): " + const_ops);
        System.out.println("O(log n): " + log_ops);
        System.out.println("O(n): " + linear_ops);
        System.out.println("O(n log n): " + nlogn_ops);
    }
}

Когда встречается O(log n)?

• Бинарный поиск — в отсортированных массивах
• Поиск в сбалансированных деревьях — AVL, Red-Black trees
• Поиск в heap — приоритетные очереди
• Балансировка в структурах данных — B-trees
• Быстрое возведение в степень — fast exponentiation
• Алгоритмы разделяй-и-властвуй — merge sort, quick sort

Важные свойства O(log n)

• Это очень эффективная сложность для больших объёмов данных
• При n = 1 миллиард операций потребуется примерно 30 итераций
• Часто используется в системах, требующих высокой производительности
• Быстрее, чем O(n), но медленнее, чем O(1)

Пример оптимизации с O(log n)

// Линейный поиск - O(n)
public boolean linearSearch(int[] arr, int target) {
    for (int num : arr) {
        if (num == target) return true;
    }
    return false;
}

// Бинарный поиск - O(log n) (требует отсортированный массив)
public boolean binarySearchOpt(int[] arr, int target) {
    // Сначала отсортируем - O(n log n)
    Arrays.sort(arr);
    // Потом ищем - O(log n)
    return Arrays.binarySearch(arr, target) >= 0;
}

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